Advanced Trees

Choose by update behavior

RangeMinQuery interleaves assignments and inclusive queries. StaticRangeMin has no updates. Same result type; different reuse strategy.

Segment nodes summarize exact intervals

[6,2,7,4,9,1], query [1,4]: combine [1,1]:2, [2,2]:7, [3,4]:4 → 2. Full cover returns a node; partial cover descends; no cover contributes +infinity.

Assignments can raise minima

Set index 1 to 8: query [1,4] becomes 4. Recompute each ancestor from both children. min(old,new) keeps stale minima. Build O(n), query/update O(log n), space O(n).

Sparse blocks overlap safely only for suitable operations

st[k][i] stores a length-2^k block. Combine adjacent halves to build. [1,5] has length 5: use length-4 blocks [1,4] and [2,5]. Minimum tolerates duplicates; sum does not. Build O(n log n), query O(1).

Reconstruct independently

[2,4] uses length-2 blocks [2,3] and [3,4]; answer 4. After setting indices 5→10 and 1→8, root minimum is 4. Test non-power-of-two lengths, singleton queries and increasing the current minimum.