Store summaries that can be combined
Suppose an array changes between range queries. For sums, an inverse lets
us subtract two prefix totals. For other summaries there may be no inverse.
Knowing prefix minima, for example, does not reveal every interval minimum:
arrays [1,5,7] and [1,2,3] have identical prefix-minimum arrays, but
their minima over indices are 5 and 2.
A segment tree takes a different route. It stores summaries of aligned intervals and answers a query by combining a small collection of disjoint intervals. A point assignment changes only the summaries of intervals containing that point. The central requirement is that summaries combine associatively; commutativity and subtraction are not required.
We use an array with and zero-based indices. All ranges are half-open: contains , with . In particular, is empty. A point assignment replaces one existing ; it is not necessarily an addition to its old value.
The algebraic contract: an associative operation and identity
Definition 1.3.1
(A monoid of range summaries)
Let be a set of summaries with a binary operation . Require associativity,
and an identity satisfying . The aggregate of a range is its left-to-right product under ; the empty range has aggregate . Such a structure is called a monoid. It need not satisfy .
Each array entry supplies one summary. The summary may be the value itself or a richer object that carries enough information for a correct merge.
| Range question | Summary and merge | Identity |
|---|---|---|
| Sum | Numbers, addition | |
| Minimum | Extended real values, minimum | |
| Maximum | Extended real values, maximum | |
| Ordered concatenation | Strings, left string followed by right string | Empty string |
| Fixed-size matrix product | Square matrices of one fixed size, multiplication | Identity matrix |
| Mean | Pairs , add sums and counts separately |
For a mean, extract only after querying and only when . Merging means alone by taking their unweighted average is wrong when the represented groups have different sizes. Associativity is a property of the summary representation, not merely the name of the requested statistic.
The mathematical sum examples use exact arithmetic. Floating-point addition is not exactly associative, so its result can depend on the tree's parenthesization. An implementation must specify its numeric interpretation and use a range sufficient for stored integer sums.
Pad to a complete binary tree
Let be the smallest power of two at least . Since , . Use array positions for the tree; position 0 is unused. Put input summaries at leaves for , and identity summaries at the remaining leaves.
For every internal position , its left child is , its right child is , and
The left child always represents the earlier interval. Every node stores the aggregate of its aligned leaf interval in that order. Padding with identities does not alter input aggregates.
BUILD(a[0..n-1]):
m = smallest power of two with m >= n
T[1..2m-1] = identity summaries
for i = 0 to n-1:
T[m+i] = summary of a[i]
for v = m-1 down to 1:
T[v] = T[2*v] star T[2*v+1]
Point assignment recomputes ancestors
ASSIGN(i, newValue): // 0 <= i < n
v = m + i
T[v] = summary of newValue
v = floor(v / 2)
while v >= 1:
T[v] = T[2*v] star T[2*v+1]
v = floor(v / 2)
Proposition 1.3.2
(Invariant of the padded tree)
For every node of the padded tree, let be the left-to-right aggregate of the aligned block of leaves below , with identities at padded leaves. Then after BUILD, and again after every ASSIGN.
Proof
(Induction from the leaves, and only ancestors change)
Build. Induction from the leaves proves the interval-summary invariant: the children hold adjacent intervals, and the parent's merge holds their concatenated aggregate. Associativity ensures that this tree grouping equals the desired left-to-right product.
Assignment. Only ancestors of leaf contain the changed entry. Other node intervals are disjoint from it and retain correct summaries. Recomputing parents bottom-up restores the invariant at each affected level. This proves assignment correctness without assuming an inverse or interpreting newValue as a delta. ∎
For , the root is already the leaf and there are no parents to recompute. The same code still works.
Why iterative queries need two accumulators
Start with the leaf-index range , . Keep a left accumulator and a right accumulator. Add a block taken from the left boundary to the end of the left accumulator; add a block taken from the right boundary to the front of the right accumulator.
QUERY(l, r): // 0 <= l <= r <= n
L = l + m
R = r + m
left = e
right = e
while L < R:
if L is odd:
left = left star T[L]
L = L + 1
if R is odd:
R = R - 1
right = T[R] star right
L = floor(L / 2)
R = floor(R / 2)
return left star right
Below the root, an odd is a right child whose left sibling is outside the remaining query. Its whole block must be taken now; if is the root itself, taking it simply finishes that whole remaining block. If is odd, node is the excluded right boundary, and its left sibling at is the last included node; that block must also be taken before ascending. Afterwards both boundaries are even, so the remaining adjacent pairs can be replaced by their parents.
Concept lensCombinatorial
The range as a union of dyadic blocks
The query takes at most one block per level from each boundary, so is a disjoint union of aligned blocks. Read in array order, their sizes first do not decrease (blocks from the left boundary, found while climbing) and then do not increase (blocks from the right boundary). For the sizes are : b, cd, ef, g. The two accumulators hold exactly the two halves of this sequence.
Proposition 1.3.3
(Ordered range query)
Assume the invariant of the padded tree. For , QUERY(l, r) returns the left-to-right aggregate of the half-open range, which is when . It takes at most two blocks per level, so it uses merges.
Proof
(Coverage and order of the two accumulators)
At the start of each iteration, the original query aggregate equals
The central blocks are the nodes from through at the current level, in order. Initially they are exactly the requested leaves, and both accumulators are identities.
Taking an odd left boundary removes the first central block and appends
it to left. Taking an odd right boundary removes the last central
block and prepends it to right. Neither skips or repeats a leaf, and
neither changes order. Once the endpoints are even, pairing children
into parents preserves the same ordered central aggregate by the stored
node invariant. Associativity permits these regroupings.
When no central blocks remain, left star right is the original range
aggregate. For an empty query the loop never runs, and it returns
. The proof never interchanges two blocks, so it does not
require commutativity.
The loop ends: after iterations while , so fails once . Each iteration takes at most two blocks, which gives the stated cost. ∎
Proof X-ray
Where the two-accumulator proof uses each hypothesis
The one non-obvious move is to keep two accumulators, appending a left block to the end of left and prepending a right block to the front of right. The loop works inward from both ends, so blocks arrive as in the trace below rather than in array order. The invariant, not the code, justifies the prepending: it says exactly where the remaining central blocks sit between the two accumulators.
Associativity is used only when two children are replaced by a parent and when the final product is regrouped. The identity is used for the empty accumulators and the padded leaves. Commutativity is used nowhere. The oddness tests carry the real content: after them and are even, so the central nodes form complete sibling pairs. Skipping the test on would leave out node ; using instead of would add an excluded leaf. The half-open convention is what makes exclusive and the condition exact.
A trace where the order matters
Worked example 1.3.4
(Concatenate indices 1 through 6)
Use eight one-character entries [a,b,c,d,e,f,g,h], so . Some
relevant stored nodes are , ,
and . Query .
| Iteration | Entering | Left block taken | Right block taken | left afterwards | right afterwards |
|---|---|---|---|---|---|
| 1 | b | g | |||
| 2 | bcd | efg |
The next boundaries are , so the result is bcd followed by efg,
namely bcdefg. Blocks were encountered in the order b,g,cd,ef, not
in their final array order. Two accumulators restore that order.
If the right update were incorrectly right star T[R], the second
iteration would give gef and the final answer would be bcdgef.
A sum or minimum query would hide this bug because those operations
commute. Ordered concatenation exposes it.
Worked example 1.3.5
(A minimum over a padded tree)
Let and with the minimum summary, so . The leaves hold , and hold . Then , and . Query starts at . Iteration 1: is even, is odd, so and ; the pair becomes . Iteration 2: both even, giving . Iteration 3: is odd, so and ; the pair becomes . The answer is , which is correct. The padded leaves were never read.
Worked example 1.3.6
(One entry and the empty range)
Let with sums and , so and . The query has . Here is odd, so and ; is even. Both halve to and the answer is . The query has , the loop never runs, and the answer is . For ASSIGN(0, 9), is set to and the next ends the loop at once, since there are no parents to recompute.
Common mistake
(Taking T[R] instead of T[R-1])
At an odd the node itself lies just outside the range; the last included node is , and the code first decrements . In the eight-letter trace the first right boundary is , and is index , outside . Taking it would put a character into the answer that the range does not contain.
Common mistake
(Reading the range as closed)
The query excludes . To concatenate indices through one must call QUERY(1, 7). Calling QUERY(1, 6) on the eight letters returns bcdef and silently drops g. An implementation that also accepts closed ranges needs the conversion at the boundary.
For fixed-size noncommutative summaries, affine maps provide another example. Represent by , with merge defined to apply the left map first and the right map second:
Composition is associative and the identity is . Its order matters: followed by gives , whereas reversing them gives . The query code works with either this convention or a matrix-product convention, provided the stored merge and requested left-to-right aggregate use the same definition. For column vectors, applying matrix first and second means the matrix product , so that action convention must not be confused with an array query explicitly requesting the product .
The figure below traces the same eight-letter query used in the solved exercises and demonstrates the affine composition method used there. Attempt those exercises first if you want independent practice.
State what the complexity counts
The tree has summary slots. Building uses merges. Assignment recomputes ancestors. A query takes at most two blocks at each level, giving merge operations and loop steps. For or an empty range, there is still a constant amount of work.
These become build time and space, and update/query time, when a summary has constant size and a merge costs constant time. Fixed-size sums, minima and fixed-size matrices meet that model under the specified arithmetic assumptions. Materializing long concatenated strings does not: merging copies characters, and returning characters costs at least . The string trace proves ordered correctness; it does not promise a logarithmic-time materialized substring operation or linear total character storage across all tree nodes. For one-character leaves with a power of two, each level alone stores characters, giving total materialized characters for .
Changing an update type requires additional algebra
Counterexample mode
Averages alone are not an associative summary
Suppose a merge is defined as . For three inputs , merging the first two and then the third gives 3, while merging the last two first gives . The actual mean is 2. This operation is neither an associative merge nor a correct way to combine unequal-sized groups.
Instead represent every input by . Merge by adding the two coordinates and use identity . The query result carries the total sum and the correct count, so mean extraction after the query is valid for a nonempty range. An empty range has no defined mean, even though its summary is well defined.
The algorithms above implement point assignment. They do not already implement range updates by changing a cached node arbitrarily. For a range addition of , a sum summary needs its actual input count : becomes . The same addition distributes correctly over the merge of adjacent summaries, and two such additions compose by adding their tags.
This compatibility between an update, a summary merge and update-tag composition is what a lazy-propagation implementation must establish. If is the action of update tag on a summary, one clean sufficient contract for a uniform monoid-action design is
In this design, the identity tag acts as the identity map. Other lazy designs can instead restrict actions to nonempty segments or carry additional length metadata, with their own compatibility proofs. Pending tags also require push-down or another tag-aware evaluation before partially covered queries or updates use child summaries; the plain query code above does not perform that bookkeeping. An update-tag composition need not commute. Merely having an associative query operation does not supply those extra update rules automatically.
Solved exercises
Quick check
(1. Recover the mean from a valid summary)
Three inputs are . Give each leaf's sum/count summary, the merged summary and the mean. Compare with the two possible repeated unweighted averages. What should an empty-range mean query report mathematically?
Solution · Solution 1
Leaves are and the merged result is , giving mean 5. The two repeated averages are and , neither of which is correct. An empty range has summary but no defined mean; it must not be reported as mean zero.
Quick check
(2. Explain the direction of the right accumulator)
In the eight-letter trace, after the first iteration right is g.
The next right block is ef. Why must the update produce efg instead
of gef? Would testing only integer sums reveal this particular error?
Solution · Solution 2
The newly selected block covers indices 4 and 5, earlier than index 6
already stored in right. It must be prepended. Integer addition is
commutative, so the wrong order gives the same sum and would not expose
this error. The proof requires order even when a particular operation
makes it invisible.
Quick check
(3. Assignment changes a query without changing its endpoints)
Use minimum summaries for [8,3,6,2,7,4,5,9]. Find the query .
Assign index 3 the new value 10 and find that query again. What is the
whole-array minimum afterwards?
Solution · Solution 3
Initially the queried entries are , with minimum 2. After assignment they are , with minimum 4. The whole-array minimum is still 3, at index 1 outside the query. Recomputing the changed leaf's ancestors restores both results; returning the root for every range would give the wrong queried value.
Quick check
(4. Aggregate affine maps in the declared order)
With , combine , and in that array order. Give the resulting map and its value at 2. Why may the tree change parentheses but not order?
Solution · Solution 4
First , then , whose value at 2 is . Associativity of composition allows either parenthesization. Commutativity fails, so reordering the maps would describe a different query. The identity map makes padding and empty ordered products consistent.