Implement tree ops and LRU cache

Question

Implement set(index) and clear(index) for the leaves of a full binary tree initially filled with 0s, where a parent node becomes 1 only when both children are 1; clearing a leaf should update ancestors accordingly. LeetCode 146. LRU Cache: Design and implement a data structure that supports get(key) and put(key, value) in O(1) time while evicting the least-recently-used item when the capacity is exceeded.

https://leetcode.com/problems/lru-cache/description/

Leaf Set/Clear with AND Tree Root

You are given a full binary tree with n leaves (n is a power of two). Initially, all leaves are 0. Each internal node's value is 1 if and only if both its children are 1, otherwise 0. You must process a sequence of operations on the leaves: set(i) sets leaf i to 1, and clear(i) sets leaf i to 0 (0-indexed). After each operation, update ancestors accordingly and report the value at the root (0 or 1). Implement a function that takes n and a list of operations and returns a list of the root values after each operation.

Constraints

• 1 <= n <= 200000
• n is a power of two
• 1 <= len(ops) <= 200000
• Each operation is a pair (cmd, i) where cmd is 'set' or 'clear' and 0 <= i < n
• Updates should be O(log n) per operation; overall O(len(ops) log n)

Examples

Example 1

Input: n = 4, ops = [('set', 0), ('set', 1), ('set', 2), ('set', 3), ('clear', 1)]
Output: [0, 0, 0, 1, 0]

Explanation: Root becomes 1 only after all 4 leaves are set. Clearing index 1 resets the left child of the root to 0, so the root becomes 0.

Example 2

Input: n = 2, ops = [('set', 0), ('clear', 0), ('set', 1), ('set', 0)]
Output: [0, 0, 0, 1]

Explanation: Root is 1 only at the end when both leaves are 1.

Hints

1. Model the updates with a segment tree using bitwise AND as the merge function.
2. Store values in an array of size 2n with leaves at indices [n .. 2n-1].
3. On updating a leaf, recompute ancestors up to the root, and you can stop early if a node's value does not change.

Approach

Use a segment tree where leaves store the given leaf values and each internal node stores the bitwise AND of its two children. A 'set' or 'clear' operation updates one leaf and then recomputes the AND values on the path to the root. The root value after each operation is the AND of all leaves, which we append to the result.

• Time complexity: O(q log n), where q = len(ops)
• Space complexity: O(n)