Segment Tree: Update a Range Now, Pay Later

A segment tree is a data structure for maintaining information about intervals of an array while supporting queries and updates efficiently. Instead of scanning every element whenever a request covers a range, the tree organizes the array into a hierarchy of segments and reuses summaries that have already been computed.

A battlefield HP model makes the idea intuitive. Imagine an ordered line of units, towers, or enemies. Each position stores one unit's current health points. A game system may need to answer questions such as:

• What is the total HP from position $l$ through position $r$?
• What is the minimum HP in that interval?
• What is the maximum HP in that interval?
• What is the HP of one particular unit after a point update?
• What happens when every unit in a whole interval takes damage?

The first three are range queries. Changing one position is a point update. Changing every position in an interval is a range update. Segment trees support these operations by combining information about smaller intervals into information about larger ones.

The phrase update a range now, pay later refers especially to lazy propagation. When a large interval receives an update, the tree does not always push that update down to every individual position immediately. Instead, it records pending work at a higher node and postpones distributing it until a later operation actually needs more detail. The update is logically applied immediately, but some physical bookkeeping is deferred.

1. The problem a segment tree solves​

Suppose an array stores battlefield HP:

[8, 3, 6, 2, 9, 4, 7, 5]

The array has $n = 8$ positions. A query for the total HP from positions $2$ through $6$ requires adding several values. If queries are rare, a direct scan is adequate. However, if a program receives many queries and updates, repeatedly walking through every requested interval can become expensive.

For a range sum query over an interval containing $k$ elements, a direct scan costs $O(k)$. In the worst case, $k$ may be $n$, so one query can cost $O(n)$. If there are $q$ operations, the total work can approach $O(nq)$.

A segment tree stores aggregate information for intervals arranged as a binary tree. Each internal node represents a segment of the array, and its two children represent the left and right halves of that segment. For sums, a parent stores the sum of its two children. For minimum queries, a parent stores the smaller child value. For maximum queries, a parent stores the larger child value.

The tree therefore stores answers for many useful intervals in advance. A query can combine a small number of these precomputed nodes instead of visiting every element one by one.

2. The shape of the tree​

Consider the eight-position HP array again. The root represents the entire interval $[1,8]$. It splits into two children:

• The left child represents $[1,4]$.
• The right child represents $[5,8]$.

Each of those segments splits again:

• $[1,4]$ becomes $[1,2]$ and $[3,4]$.
• $[5,8]$ becomes $[5,6]$ and $[7,8]$.

Finally, each two-position interval splits into individual positions:

                         [1,8]
                       /       \\
                    [1,4]     [5,8]
                   /    \\     /    \\
                [1,2] [3,4] [5,6] [7,8]
                /  \\  /  \\  /  \\  /  \\
              [1] [2][3][4][5][6][7][8]

This is a balanced binary tree when the array is divided approximately in half at each level. Its height is $O(\log n)$ because the interval size is roughly halved on every level.

The exact tree is not required to be perfect when $n$ is not a power of two. An array with seven positions still divides recursively until every leaf represents one position. Some branches may end one level earlier than others, but the height remains $O(\log n)$.

A node has three important pieces of structural information:

1. The interval boundaries, usually written as $[L,R]$.
2. The aggregate value for that interval.
3. For lazy propagation, a record of updates that still need to be passed to descendants.

The aggregate is not necessarily a sum. It could be a minimum, maximum, greatest common divisor, or another operation that can combine child results correctly. The update rules depend on the chosen aggregate, so a segment tree is best understood as a framework rather than one single fixed data structure.

3. The interval invariant​

The most important invariant is that each node accurately represents its assigned interval according to the chosen aggregate.

For a sum segment tree, the invariant is:

where $M$ is the midpoint used to split the interval.

For a minimum segment tree, the invariant becomes:

For a maximum segment tree, it becomes:

This parent-child relationship is what makes the tree useful. If the children are correct, the parent can be rebuilt by applying the aggregate's combination rule.

A leaf represents one array position. If position $i$ currently has HP $h_i$, the leaf for $[i,i]$ stores $h_i$. Internal values are built upward from these leaves.

For the sample HP array, the root sum is calculated as follows:

The tree stores partial results such as the sum for $[1,4]$ and the sum for $[5,8]$, not just the total for the entire array.

4. Building the tree​

A segment tree is usually built recursively. The build procedure receives a node interval $[L,R]$.

• If $L=R$, the interval is a leaf, so the node receives the corresponding array value.
• Otherwise, compute a midpoint $M$, build the left interval $[L,M]$, build the right interval $[M+1,R]$, and combine the two child values.

The recursion visits every relevant node once. There are $O(n)$ leaves and fewer than $O(n)$ internal nodes, so construction takes $O(n)$ time. The memory requirement is also $O(n)$, commonly implemented with an array somewhat larger than the original array to hold the tree nodes.

The tree's height is $O(\log n)$, but building it is not merely a root-to-leaf operation. It processes all nodes, which is why its total time is $O(n)$ rather than $O(\log n)$.

A build operation for a sum tree can be summarized as follows:

build(node, left, right):
    if left == right:
        tree[node] = array[left]
        return

    middle = midpoint(left, right)
    build(left child, left, middle)
    build(right child, middle + 1, right)
    tree[node] = tree[left child] + tree[right child]

The exact indexing scheme is less important than the structural rule: leaves take values directly, and internal nodes combine their children.

5. Range queries through exact coverage​

A range query asks for an aggregate over a target interval $[q_L,q_R]$. At each visited node, compare the node interval $[L,R]$ with the target. There are three cases.

Case 1: No overlap​

If the node interval and query interval do not intersect, this node contributes nothing to the answer. For a sum query, the neutral contribution is zero. For a minimum or maximum query, the appropriate neutral value must be chosen so that it does not incorrectly change the result.

For example, a node representing $[1,3]$ has no overlap with a query for $[5,7]$. There is no reason to descend into that node.

Case 2: Complete coverage​

If the query interval completely contains the node interval, use the node's stored aggregate immediately. This is the key performance advantage.

If a node represents $[3,4]$ and the query is $[2,7]$, then the whole node is inside the requested range. Its stored value already summarizes both positions, so there is no need to inspect its children.

Case 3: Partial overlap​

If the intervals intersect but neither completely contains the other, split the search into the two children. Combine the answers returned by the left and right subtrees.

For a sum query requesting $[2,7]$ on the eight-position array, the tree can use several complete segments, such as $[2,2]$, $[3,4]$, $[5,6]$, and $[7,7]$, or an equivalent collection based on the tree shape. It does not need to scan all six positions as individual leaves if larger pieces are fully covered.

A balanced segment tree decomposes a query interval into a limited number of canonical segments. The recursive search follows only relevant branches, giving a query time of $O(\log n)$ in the standard segment-tree analysis. The traversal can branch, so it is not literally just one root-to-leaf path, but the balanced structure limits the total relevant work to logarithmic order for a single interval query under the usual model.

6. Point updates​

A point update changes one position, such as changing the HP at position $5$ from $9$ to $6$.

Only the leaf for position $5$ changes directly. Every ancestor of that leaf may need to be rebuilt because its aggregate includes position $5$. The update follows one root-to-leaf path:

1. Start at the root interval.
2. Determine whether the target position is in the left or right half.
3. Recurse into that child.
4. Continue until the leaf is reached.
5. Replace the leaf value.
6. Recompute each ancestor while returning from the recursion.

For the sample array, changing position $5$ affects the intervals $[5,5]$, $[5,6]$, $[5,8]$, and $[1,8]$. It does not affect $[1,4]$ because that segment contains no changed position.

Because the tree height is $O(\log n)$, a point update costs $O(\log n)$. This is much faster than changing the array and recomputing every aggregate interval from scratch.

The invariant after a point update is the same as before: every node must again contain the correct aggregate for its interval. Recomputing ancestors is what restores that invariant.

If a point update is performed on a tree that also uses lazy propagation, pending updates on the path must be handled correctly. Before descending through a node, deferred work may need to be pushed so that the target leaf reflects the current logical value. After the leaf changes, ancestors are rebuilt using their now-correct children.

7. Why range updates are more difficult​

Now suppose every unit from position $2$ through position $6$ takes $3$ damage. A range update modifies several leaves at once:

positions:  1   2   3   4   5   6   7   8
before:     8   3   6   2   9   4   7   5

After subtracting $3$ from positions $2$ through $6, the logical array is:

positions:  1   2   3   4   5   6   7   8
after:      8   0   3  -1   6   1   7   5

If the implementation walks to every affected leaf, the operation can cost $O(n)$ in the worst case. That may be acceptable for a few updates, but repeated range updates can again lead to large total work.

The segment tree already contains nodes representing groups of positions. If an entire node interval lies inside the update interval, it would be wasteful to immediately visit every descendant. The node's aggregate can often be adjusted directly, while the fact that all descendants also need the update is recorded for later.

That deferred record is the lazy value.

8. Lazy propagation: applying logically, postponing physically​

Lazy propagation adds a pending-update marker to a node. For a range-add operation, the marker may mean that every value in this node's interval still needs an increment or decrement.

Consider a node representing $s$ units with total HP $T$. If every unit takes damage $d$, then the new sum is:

More generally, if an interval contains $s$ elements and every element receives an additive update $d$, then:

The node's stored sum can therefore be updated immediately. The implementation also stores $d$ as a pending operation at that node. The descendants have not necessarily been modified yet, but the node's aggregate is already correct for the whole interval.

This is the meaning of pay later. The cost of distributing the update to all leaves is postponed. If a future operation never needs to inspect those descendants, the distribution may never be necessary.

For a sum tree supporting range addition, a fully covered node can be handled in constant time:

apply(node, interval length, delta):
    tree[node] += interval length * delta
    lazy[node] += delta

The aggregate update and lazy-marker update must agree. Updating only the aggregate would lose information about descendants. Updating only the lazy marker would make the node's own stored answer stale.

9. Pushing a deferred update downward​

Eventually, a query or update may partially enter a node whose lazy marker is nonzero. At that point, the children must learn about the pending operation before their values are used. This action is called pushing or propagating the lazy value.

Suppose a parent has a pending additive update $d$. Its left child covers $s_L$ elements, and its right child covers $s_R$ elements. Applying the marker to the children means:

After passing the work down, the parent's lazy marker is cleared. The parent itself remains correct because its children now collectively represent the deferred update.

A conceptual push operation is:

push(node):
    if lazy[node] is neutral:
        return

    apply pending update to left child
    apply pending update to right child
    lazy[node] = neutral

The neutral lazy value depends on the update type. For additive updates, it is zero because adding zero changes nothing. For assignment updates, a separate marker is often needed to distinguish no pending assignment from an assignment whose value happens to be zero.

Pushing is not performed everywhere after every update. It is performed only when descending into children and the children need current information. This is where the deferred work is paid for.

10. A small lazy-propagation example​

Imagine a node representing positions $1$ through $4$, with HP values $[8,3,6,2]$. Its sum is $19$. Every position in this interval takes $2$ damage.

The new values are logically $[6,1,4,0]$, and the new sum is:

A lazy segment tree can change the node's stored sum from $19$ to $11$ and record a pending update of $-2$. It does not need to immediately change the four leaves.

Now suppose a later query asks for the sum over positions $1$ through $4$. The node is completely covered, so the stored value $11$ is returned immediately. No push is needed.

Suppose instead that a later query asks only for position $2$. The search must descend. Before entering the relevant child, the pending $-2$ is pushed to the children. The child covering positions $1$ and $2$ receives the update, and then the leaf for position $2$ can be reached with the correct value.

The deferred update did not change the logical result. It changed when the implementation performed the detailed work.

11. Complexity with lazy propagation​

For a segment tree with range updates and range queries, lazy propagation generally gives $O(\log n)$ time per standard range operation under the supported update and aggregate rules.

The intuition is that a range update uses fully covered nodes whenever possible. Only boundary regions tend to require recursive descent. Pending updates prevent the implementation from repeatedly visiting every leaf in the middle of the target interval.

The usual costs are:

• Build: $O(n)$ time.
• Point update: $O(\log n)$ time.
• Point query: $O(\log n)$ time.
• Range query: $O(\log n)$ time in the standard balanced-tree analysis.
• Range update with lazy propagation: $O(\log n)$ time in the standard supported setting.
• Storage: $O(n)$.

The total cost for $q$ operations after construction is often described as $O(n + q\log n)$ when every operation fits the tree's supported update and query model.

These bounds depend on maintaining the correct invariants and using a compatible lazy-update rule. A segment tree cannot automatically defer every possible operation. The aggregate must be updateable from a node summary, and pending updates must be composable in a way that preserves correctness.

The complexity guarantee is therefore not supplied by recursion alone. It comes from the combination of a balanced interval decomposition, constant-time handling of fully covered segments, and lazy markers that prevent unnecessary descent into the interior of an updated range.

12. Aggregate choices and their consequences​

The same tree shape can support different aggregates, but the combine and update logic changes.

Sum​

For sums, combining children means addition. A range-add update is especially natural because adding $d$ to every element in a segment containing $s$ positions changes the sum by $s\cdot d$.

Minimum​

For a minimum tree, combining children means taking the smaller value. If the same value $d$ is added to every element in a segment, the segment minimum also increases by $d$. Thus a lazy additive marker can often update the stored minimum directly.

Maximum​

For a maximum tree, combining children means taking the larger value. A uniform additive update similarly shifts the maximum by $d$.

Other aggregates​

Some operations need more information than one number. An operation involving both range addition and range assignment may require carefully designed lazy markers because assignment replaces earlier values while addition modifies them. The order of pending operations matters.

The practical lesson is to define four rules before implementing a tree:

1. How two child aggregates combine.
2. How a full-segment update changes one node's aggregate.
3. How two pending updates compose.
4. How a pending update is pushed to children.

If any one of these rules is unclear, the implementation is not ready. Most bugs in lazy segment trees are invariant or composition bugs rather than recursion bugs.

13. Update composition and ordering​

Consider two range-add updates. First add $a$, then add $b$. The final effect is adding $a+b$, so additive lazy markers can be combined by addition:

The order does not matter for ordinary addition.

Assignment updates are different. Suppose a segment is first assigned the value $x$ and then receives an addition of $d$. The final value is $x+d$. If it is first increased by $d$ and then assigned $x$, the final value is simply $x$. Therefore, these operations are not interchangeable.

A correct implementation must preserve chronological meaning when composing markers. A newer assignment may override an older assignment and may also interact with an older additive marker. The exact marker structure depends on the supported operation set, but the principle is universal: pending updates are a compact representation of operations that must produce the same result as if they had been applied directly.

This is particularly important when several updates cover the same large node before any query descends into it. The node may hold only one compact marker or a small combination of markers, but that representation must preserve the effect of the entire update sequence.

14. Query correctness with pending markers​

A common concern is whether a node with an unapplied lazy marker can safely answer a query. The answer is yes if the node's aggregate has already been adjusted to include the pending operation.

For a fully covered query, the node summary is sufficient. The descendants can remain stale because the query does not inspect them.

For a partially covered query, the implementation must push before asking the children for answers. Otherwise, a child may return an old value that does not include the pending update.

This gives a useful invariant:

A node's stored aggregate is always correct for its entire interval. Its descendants may lag behind only when the node carries a pending marker that explains the difference.

Pushing restores consistency between the node and its children. It does not change the logical array; it only moves deferred information down the tree.

A useful way to test this invariant is to imagine expanding every pending marker all the way to the leaves. The expanded state should be exactly the logical array after all requested operations. Lazy propagation is correct when the compact tree and this fully expanded interpretation always agree on every query.

15. Boundary handling​

Range structures are especially sensitive to interval conventions. Choose one convention and use it everywhere.

A common choice is inclusive intervals $[L,R]$. Under this convention:

• A leaf has $L=R$.
• The midpoint divides the interval into $[L,M]$ and $[M+1,R]$.
• A query is fully covered when $q_L\le L$ and $R\le q_R$.
• There is no overlap when $R<q_L$ or $q_R<L$.

Another choice is half-open intervals $[L,R)$, where the right endpoint is excluded. That convention can also work, but mixing inclusive and half-open logic creates off-by-one errors.

For the battlefield interpretation, write down clearly whether a request for positions $2$ through $6$ includes both positions. Most descriptions of indexed battlefield positions use an inclusive range, but the implementation must follow the selected convention consistently.

The midpoint also deserves care. For inclusive intervals, a conventional midpoint separates the children into $[L,M]$ and $[M+1,R]$. The recursion must stop when $L=R$; otherwise an interval of one position can be split forever.

16. A practical operation checklist​

When processing a range query or update, use the following mental checklist:

1. What interval does the current node represent?
2. Does the requested interval miss it completely?
3. Does the requested interval cover it completely?
4. If the operation is partial, has a pending marker been pushed first?
5. What are the answers or updates for the two children?
6. How should the parent be rebuilt from those children?

For a point update, ask a similar set of questions:

1. Is the current node a leaf?
2. Which child contains the target position?
3. After updating that child, what is the parent's new aggregate?

These questions directly mirror the tree invariant and make the recursion easier to reason about. They also provide a practical debugging strategy: inspect one interval, one aggregate, and one pending marker at a time rather than treating the whole tree as an opaque recursive structure.

17. Common mistakes​

Forgetting segment length​

For a sum tree, adding $d$ to every value in a segment changes the sum by the number of elements times $d$. Updating the node by only $d$ is wrong unless the segment contains one element.

Updating a node but not its lazy marker​

If the aggregate changes but the deferred marker does not, a later push will fail to inform the children. The parent may look correct temporarily, while future partial queries return incorrect results.

Pushing too late​

When a query or update descends into children, any pending parent update must be transferred first. Otherwise, the descendants do not represent the current logical array.

Rebuilding incorrectly​

After children change, the parent must be recomputed using the exact aggregate rule. A sum parent uses addition; a minimum parent uses the smaller child; a maximum parent uses the larger child.

Confusing assignment with addition​

Assigning every HP value in a segment to $x$ is not the same as adding $x$. Assignment replaces old values, while addition preserves them and shifts them. Their lazy markers compose differently.

Ignoring neutral values​

No-overlap queries need a neutral result. For sums, zero is natural. For minimum and maximum, choose values that cannot incorrectly dominate a real answer. This choice is part of the aggregate design.

Mixing index conventions​

Many bugs come from using one-based intervals in one function and zero-based array positions in another without a carefully defined translation. The segment boundaries, leaves, and query endpoints must agree.

Forgetting to clear a marker after pushing​

Once a pending update has been transferred to both children, the parent's marker must be reset to its neutral state. If it is left in place, a later descent can apply the same update again.

Treating a stale child as an error by itself​

A child may not yet include a parent's pending update. That is intentional as long as the parent marker accurately records the difference and the parent aggregate is correct. The child becomes required to be current only when an operation descends into it.

18. When a segment tree is a good fit​

A segment tree is useful when all of the following are present:

• Data is arranged in an ordered sequence.
• Operations ask about contiguous intervals.
• Values change over time.
• Queries and updates are frequent enough that repeated scanning is too slow.
• A segment's answer can be summarized and combined from child summaries.

The battlefield HP example fits naturally because units occupy ordered positions, damage may affect a contiguous region, and the program may need totals, minimums, or maximums after many changes.

A segment tree may be unnecessary when the array never changes and a simpler preprocessing method answers queries adequately. It may also be excessive when the input is tiny. The right data structure depends on the operation mix, constraints, and aggregate rules.

It is also important to distinguish a point-update problem from a range-update problem. A basic segment tree without lazy propagation is often enough for point updates and range queries. Lazy propagation becomes useful when entire intervals are updated and those updates would otherwise force a visit to many leaves.

19. The central mental model​

The most useful way to remember a segment tree is not as a complicated recursive program. Think of it as a hierarchy of interval summaries.

• Leaves know individual positions.
• Internal nodes know summaries of larger intervals.
• Queries choose a collection of nodes whose intervals exactly cover the request.
• Point updates repair one path to the root.
• Range updates use fully covered nodes whenever possible.
• Lazy propagation records work that is logically done but physically postponed.

The tree does not eliminate work. It organizes work so that repeated operations reuse summaries and avoid unnecessary descent. Lazy propagation goes one step further: it avoids distributing an update into details that no future operation has requested yet.

In the HP example, a node might represent four neighboring units. If all four take damage, the group total can be corrected immediately. The individual unit records may wait. If headquarters asks only for the group's total HP, no additional work is needed. If a commander asks about one unit, the pending damage is passed down along the relevant path.

This separation between logical state and physical detail is the heart of deferred updates. The data structure does not pretend that the update did not happen. It records enough information to answer whole-segment questions correctly while postponing the expansion of that information into smaller segments.

20. Final takeaway​

A segment tree combines a balanced interval decomposition with a carefully maintained invariant. The shape is a binary hierarchy: each interval is split into two smaller intervals until leaves represent individual array positions. The stored value at each parent is derived from its children according to the chosen aggregate.

Range queries use three coverage cases: no overlap, complete coverage, and partial overlap. Complete coverage is where precomputed interval summaries save time. Point updates change one leaf and rebuild its ancestors, costing $O(\log n)$.

Range updates are more demanding because many leaves may change. Lazy propagation addresses this by updating a fully covered node's summary immediately while storing a pending marker for its descendants. If a later operation needs to descend, the marker is pushed downward. The logical update happens now; the detailed propagation is paid for later, and only when necessary.

For a standard supported configuration, construction costs $O(n)$, storage costs $O(n)$, and range queries, point updates, and lazy range updates can be handled in $O(\log n)$ time. The real skill lies in preserving the invariants: every node summary must be correct, every pending marker must describe deferred work accurately, and every update composition must preserve operation order.

In battlefield terms, the tree keeps reports for groups of units. When an entire group takes damage, the group report changes immediately, while the individual reports may wait. If headquarters asks only for the group's total HP, the group report is enough. If a commander asks about one unit, the deferred damage is passed down along the relevant path. That is the practical meaning of update a range now, pay later.