Why prefix minima do not subtract
Let be real numbers, where . We need two operations: replace by a specified value, and find for . The preceding Fenwick-tree lesson explains why two prefix minima do not determine an arbitrary interval minimum. That limitation does not prevent other data structures from solving this task.
A segment tree stores information for a family of nested intervals. We use ordinary point assignment, not an increment. The tree described here is a different structure from the Fenwick tree; it makes range minimum and assignment direct through its stored invariant.
Build and invariant
Definition 1.2.1
(Minimum segment tree)
Let be real numbers with . The minimum segment tree is the binary tree whose root represents . A node for with has children and , where . A leaf stores , and every internal node stores the minimum of the stored values of its two children. The value stored at a node is written .
By induction on the tree, from the leaves upward, the stored values satisfy the invariant
The intervals partition their parent; no element is dropped or counted outside its interval. Repeated splitting ends at exactly leaves. Since each internal node has two children, the tree has nodes and can be built bottom-up in time and space.
To assign , descend through the unique child containing , replace the leaf value by , then recompute the minima on the path back to the root. Leaves outside that path are unchanged. On the path, each recomputation restores the invariant from the already correct children; thus the root and all other nodes are correct after the update. This works whether increases or decreases the old value.
Query and its cost
To query , visit the root recursively. For a node interval :
- if is disjoint from , return ;
- if , return its stored minimum;
- otherwise return the minimum of the two children's results.
The symbol is a conceptual identity for the minimum, not an array value: . The public query requires a nonempty valid interval, so its final answer is finite. An implementation can instead represent a disjoint result with an explicit empty flag.
Proposition 1.2.2
(Correctness and cost of the minimum segment tree)
Let the minimum segment tree on satisfy the invariant, and assume that comparison, indexing and storage of one number take constant time.
- After the point assignment described above, the invariant holds again for every node.
- For the query returns .
- The tree has height at most , a query visits at most four nodes at each depth, and an assignment visits one node at each depth. Hence both operations take time, including .
Proof
(Path recomputation, interval cover and a four-node bound)
Assignment. A node whose interval does not contain depends only on leaves other than , so its stored value is unchanged and still correct. The nodes whose intervals contain form the path from the leaf to the root. The leaf now stores . Going upward, each path node is recomputed as the minimum of its two children. One child lies on the path, and is already correct; the other lies off the path, and is unchanged and correct. The two child intervals partition the parent, so the minimum of the two stored values is the minimum over the parent. Hence the invariant holds at every node.
Query. For a visited node write for the value it returns, and let . We show by induction on the height of that . If is disjoint from , the set is empty and . If , then by the invariant. Otherwise meets without being contained in it, so has at least two elements and is internal. Its two child intervals partition , hence is the disjoint union of and , and the minimum of the two child results is the minimum over the union. At the root, is nonempty, so the answer is finite.
Cost. At depth every interval has at most elements, so the height is at most . Call a node partial if it meets without being contained in it. An interval that contains an index inside and an index outside it contains two adjacent indices of which exactly one is inside, so a partial node contains both and , or both and . Node intervals at one depth are disjoint, so at most one node per depth contains and at most one contains ; thus there are at most two partial nodes per depth. The query recurses only below partial nodes, so it visits at most four nodes per depth, at most in all. An assignment follows one root-to-leaf path. Each visit costs constant time. ∎
Proof X-ray
What the query induction needs from the min operation
The non-obvious move is to prove a statement about every visited node, not just the ones that are fully covered. Defining lets the disjoint case, the covered case and the split case share one claim, so a single induction handles all three.
The split case uses exactly two facts: the children partition , and the minimum of a union is the minimum of the two minima. Idempotence is never used, so the same proof works for any associative operation with an identity element, such as a sum with identity . The disjoint case is the reason an identity element is needed at all: it must satisfy for every .
The cost argument uses a different property of the tree: intervals at one depth are disjoint. That is what turns "a partial node contains an adjacent pair straddling or " into "at most two partial nodes per depth". Without disjointness, for example with overlapping children, the bound of four visited nodes per depth would not follow.
Two typical failures are a wrong value for a disjoint node and an update rule that is weaker than assignment. The next two blocks show one concrete instance of each.
Counterexample mode
Zero is not a safe value for a disjoint node
Claim: a node disjoint from may return , since a neutral-looking number cannot affect the answer. Take . The root has children and . Query : the root is partial, the child is covered and returns , and the child is disjoint and returns under the claim. The root then returns , but the true answer is . The same happens for any finite value on an array whose entries all exceed , because then . The disjoint result must satisfy for every , which forces , or an explicit empty flag.
Common mistake
(Treating an assignment as a decrease)
It is tempting to update each node on the path by . This is valid when does not exceed the old leaf value, but it fails for an increase. On assign . The rule keeps at the leaf and above it, so query still returns , whereas the array is now and the answer is . An increase can remove the old minimum, so each ancestor must be recomputed from both of its children.
Worked update
Worked example 1.2.3
(Query then assignment on five numbers)
Start with . The root splits into and . Querying combines the values for , and , giving . Now assign . Recompute as and the root as . The same query now returns . A point assignment does not mean adding to the old value.
Worked example 1.2.4
(The nodes visited by one query)
On the nodes are , then and , then , , , , then and . Query visits all nine. The root, , and are partial. The leaves , and are covered and return , and ; the leaves and are disjoint and return . So returns , returns , returns , and the root returns . The counts per depth are , within the bound of four.
Worked example 1.2.5
(A tree with a single leaf)
Let and . The root is also the only leaf, so it has no children and no ancestors. Query finds the root covered and returns . Assigning replaces the stored value; there is no path to recompute, so the next query returns . Both operations take constant time, which agrees with .
Exercises with solutions
Quick check
(A decrease. Starting from , assign . What are the minimum of and the root minimum?)
Solution · Answer
Both are . The array becomes ; only the ancestors of leaf need recomputing, namely and the root.
Quick check
(A full-cover query. Why does take constant time after construction?)
Solution · Answer
The root is fully covered and already stores the answer, so no children are visited.
Quick check
(One point query. On , which nodes does the query visit, and what does it return?)
Solution · Answer
It visits , , , and . The nodes and are disjoint and return , the leaf is covered and returns , so the answer is .
Quick check
(Counting nodes. How many leaves and how many nodes does the tree have for ?)
Solution · Answer
There are leaves and internal nodes, because each internal node has two children and the tree has leaves. The total is .