Advanced Trees: Dynamic and Static Range Minimum

Both exercises return minima over inclusive, zero-based ranges. The choice of structure follows whether the array changes. RangeMinQuery interleaves assignments [0,index,value] with queries [1,left,right]; StaticRangeMin receives only [left,right] queries. Prepare by tracing a binary tree and taking the minimum of disjoint array slices. Empty inputs have no valid index queries.

Define exactly what a node summarizes

A segment-tree node represents an interval [l,r] and stores the minimum of those elements. A leaf stores one value. An internal node splits at mid=l+(r-l)/2 into [l,mid] and [mid+1,r], and stores the minimum of its two children. Build children before the parent. This visits O(n) nodes and uses O(n) space; a recursive array representation commonly reserves 4n cells.

For [6,2,7,4,9,1], the relevant tree is:

[0,5]:1
  [0,2]:2                 [3,5]:1
    [0,1]:2   [2,2]:7       [3,4]:4   [5,5]:1
      6   2                    4   9

To query [1,4], [0,5] overlaps only partly, so descend. The left half yields [1,1]:2 and [2,2]:7; the right yields the fully covered [3,4]:4. Ignore [0,0] and [5,5]. Combine min(2,7,4)=2. Do not return the root's 1: its winning element lies outside the requested range.

Three overlap cases make the recursive query precise: no overlap contributes an identity; full coverage returns the cached node; partial overlap combines children. For minimum the identity is positive infinity, represented by a value at least as large as every possible element (Go's maximum int is suitable). Zero is wrong for a positive-only query. Initial dynamic-RMQ values may reach the native integer limit; Python can use float("inf") as an identity without converting the actual integer minima to floats. A guessed 10**18 fails on a valid initial value such as 1<<62. A branching implementation can avoid calling disjoint children, but still needs a valid initial result.

An assignment repairs every containing ancestor

Assign index 1 the value 8. The leaf becomes 8; [0,1] becomes 6; [0,2] becomes 6; the root stays 1 because its right child still has 1. Now [1,4] returns min(8,7,4)=4.

Recompute every ancestor from both current children. Merely taking min(oldMinimum,newValue) cannot handle increases: assigning away a previous minimum may raise the answer. An assignment is also not an increment. Only one root-to-leaf path changes, taking O(log n). A contiguous query visits O(log n) boundary nodes and their fully covered siblings, also O(log n).

An iterative tree pads leaves to a power of two. Fill extra leaves with the identity, not zero, and map real index i to size+i. It implements the same interval contract despite different node numbers. Lazy propagation is useful for a different task with range updates; this exercise needs only assignments.

Static queries reuse overlapping power-of-two blocks

Define st[k][i] as the minimum in the length-2^k block starting at i. The recurrence combines adjacent halves:

st[0][i] = nums[i]
st[k][i] = min(st[k-1][i], st[k-1][i + 2^(k-1)])

Only construct cells with i+2^k <= n. For the same original array:

Block length	Minima by starting index
1	[6,2,7,4,9,1]
2	[2,2,4,4,1]
4	[2,2,1]

For [1,5], length L=5, choose k=floor(log2 L)=2. The left block starts at 1 and covers [1,4]; the right block starts at r-2^k+1=2 and covers [2,5]. Their minima are 2 and 1, giving answer 1. The overlap [2,4] is safe because min(x,x)=x: minimum is idempotent. For sums the two blocks would double count the overlap. Associativity alone does not justify this query rule.

Build integer logs with log[1]=0, log[i]=log[i/2]+1; no floating-point rounding is needed. Preprocessing uses O(n log n) time and space, after which each minimum query uses O(1) time. An update invalidates cached blocks; changing only st[0] cannot repair them. Choose a segment tree for interleaved updates.

Finish the derivation

1. On the original array, query [2,4]. List the two length-2 sparse blocks and their minima. Which element is counted in both, and why is that harmless?
2. Assign index 5 to 10, then index 1 to 8. What is the new root minimum? Which stale value would survive if parents used min(old,new)?
3. Transfer the segment tree to sum. What is the identity? Can the sparse table's two-overlapping-block query be reused unchanged?

Check your reconstruction

1. Blocks [2,3] and [3,4] both have minimum 4. Index 3 appears twice; duplicate inclusion does not change a minimum. Result 4.
2. Final array [6,8,7,4,9,10], root minimum 4. An update that only lowers cached values incorrectly retains 1 (and may retain 2 in the left subtree).
3. Sum's identity is 0. Its segment tree still works; the overlapping sparse query does not, because repeated elements change a sum. Use disjoint blocks or another static sum representation such as prefix sums.

Implement both tasks and compare with direct range scans on small arrays, including singleton ranges, non-power-of-two lengths and increasing an existing minimum. On a later revisit, explain why storing only a minimum and its index is insufficient to update a range after that minimum increases.

An interval tree addresses a different query: find stored intervals that intersect a point or interval. It is not a substitute for these array aggregate APIs. Extending this module to interval stabbing needs its own output-sensitive contract and exercise; no implementation of it is claimed here.