The Segment Tree: One Flat Array, Every Range Query

You have an array. Someone keeps mutating elements. Someone else keeps asking for the sum of elements 3 through 7. Prefix sums give you O(1) queries, which feels great until a value changes. Your entire prefix array is stale. You rebuild in O(n). n mutations later, you've spent O(n²) total. Your next code review is going to go great.

The segment tree fixes this. It handles range sum, min, max, GCD, and XOR queries in O(log n), handles point updates in O(log n), and with lazy propagation extends to range updates in O(log n) too. The memory cost is O(n). No amortization, no tricks. Every operation is worst-case O(log n).

When you reach for it: any problem with repeated range queries on a mutable array. If you can answer "what is the aggregate over this whole segment?" and combine two adjacent answers in O(1), a segment tree works.

Every senior engineer when someone schedules a segment tree interview question. Then the stock price goes down and they understand.

The Mental Model

A segment tree is a complete binary tree built over an array of n elements. Each node stores an aggregate (sum, min, max, etc.) over a contiguous slice of the original array.

• The root stores the aggregate over the entire array.
• A node covering indices [l, r] has a left child covering [l, mid] and a right child covering [mid+1, r], where mid = (l+r)/2.
• Leaves store individual array values.

The whole tree lives in a single flat array. No node objects, no pointers, no dynamic allocation. The tree structure is implicit, encoded entirely in index arithmetic. The imposing recursive binary tree you're picturing is just index math on a plain array. Satisfying or slightly anticlimactic, depending on what you were hoping for.

The Memory Layout

Given an array arr of length n, you allocate a tree array of size 4n. The root lives at index 1. For any node at index i:

• Left child: 2i
• Right child: 2i + 1
• Parent: i / 2 (integer division)

This is the same BFS numbering used for binary heaps. You never store the segment boundaries [l, r] inside the array. They are recomputed on every traversal, passed as parameters in the recursive calls.

arr = [3, 1, 4, 1, 5]        (0-indexed)

                  [0..4] sum=14         index 1
                 /              \
        [0..2] sum=8          [3..4] sum=6    indices 2,3
        /       \              /      \
   [0..1]=4  [2..2]=4    [3..3]=1  [4..4]=5  indices 4,5,6,7
   /    \
[0..0]=3 [1..1]=1                            indices 8,9

tree array (1-indexed):
 idx:  1   2   3   4   5   6   7   8   9
 val: 14   8   6   4   4   1   5   3   1

Each tree node maps to exactly one slot in a plain array. The parent-child relationships are pure arithmetic: left child at 2i, right child at 2i+1.

Why 4n and Not 2n-1?

The tree has exactly 2n-1 nodes (n leaves plus n-1 internal nodes). So why not allocate 2n-1?

Because BFS-numbered indices do not fill a contiguous range when n is not a power of two. Nodes are numbered in BFS order starting from 1. When the tree is not perfectly balanced, some internal nodes at the second-to-last level have children at BFS positions that overshoot 2n-1. The worst case is n = 2^k + 1: the last level has very few nodes, but their BFS indices can reach close to 4 * 2^k. Allocating 4n guarantees no leaf index overflows the array, at the cost of some wasted slots. You're burning up to roughly 2n empty slots that will never be written to. This is fine. Memory is cheap. Index-out-of-bounds panics at midnight are not.

There is a cleaner bottom-up variant that places leaves at fixed positions [n, 2n) and uses only 2n total space. It is faster in practice (better cache locality, no recursion overhead) and eliminates the 4n confusion. But the recursive 4n version is what appears in most interview contexts and competitive programming writeups, so that is what we build here.

Building the Tree in O(n)

Build is a post-order traversal: recurse into both children first, then compute the current node's value from them.

build(node=1, [0..4]):
  build(node=2, [0..2]):
    build(node=4, [0..1]):
      build(node=8, [0..0])  -> tree[8] = arr[0] = 3
      build(node=9, [1..1])  -> tree[9] = arr[1] = 1
      tree[4] = 3 + 1 = 4
    build(node=5, [2..2])    -> tree[5] = arr[2] = 4
    tree[2] = 4 + 4 = 8
  build(node=3, [3..4]):
    ...
  tree[1] = 8 + 6 = 14

Build runs in O(n) because there are exactly 2n-1 nodes and each is visited once.

Here is the arithmetic. n leaves at the bottom, n/2 nodes one level up (each combining two leaves), n/4 at the level above that, continuing until the root. Summing: n + n/2 + n/4 + ... = 2n - 1 (geometric series). Each node requires O(1) work (one merge). Total: O(n). You touch every node once. The math actually checks out cleanly for once.

Range Queries: The Four-Nodes-Per-Level Argument

Range queries work by recursive overlap testing. At each node covering [start, end], given a query range [left, right]:

• If [start, end] is entirely outside [left, right]: return the identity element (0 for sum, +∞ for min).
• If [start, end] is entirely inside [left, right]: return tree[node].
• Otherwise, recurse into both children and combine.

query(sum, [1..3]) on arr=[3,1,4,1,5]:

node 1 [0..4]: partial overlap, recurse
  node 2 [0..2]: partial overlap, recurse
    node 4 [0..1]: partial overlap, recurse
      node 8 [0..0]: outside [1..3], return 0
      node 9 [1..1]: inside [1..3], return 1
    return 1
    node 5 [2..2]: inside [1..3], return 4
  return 1 + 4 = 5
  node 3 [3..4]: partial overlap, recurse
    node 6 [3..3]: inside [1..3], return 1
    node 7 [4..4]: outside [1..3], return 0
  return 1 + 0 = 1
return 5 + 1 = 6

At any level of the tree, at most four nodes are visited. Here is the proof.

The query interval [left, right] has two boundaries: a left boundary and a right boundary. As you descend, the left boundary can split a node into "both children visited" at most once per level. Once the split happens, one subtree is fully inside [left, right] and returns immediately without recursing further. The same reasoning applies to the right boundary independently. So at each depth: at most two boundary splits, each producing at most two recursive calls. Four nodes per level. The tree has O(log n) levels. Total: O(log n).

The color coding makes the four-nodes-per-level argument concrete. At every depth, the boundary splits produce at most four active nodes. Everything amber returns in O(1). Everything gray never recurses.

Point Updates: Walking the Path

A point update at index i walks from root to leaf: at each node, descend into the child whose range contains i, then recompute the current node's value on the way back up. The path has length O(log n) since the tree's height is ceil(log₂(n)). Each step is O(1). Total: O(log n).

update(index=2, value=7):
  node 1 [0..4]: 2 is in right half? No. Go left.
  node 2 [0..2]: 2 is in right half? Yes (mid=1). Go right.
  node 5 [2..2]: leaf. tree[5] = 7.
  back at node 2: tree[2] = tree[4] + tree[5] = 4 + 7 = 11
  back at node 1: tree[1] = tree[2] + tree[3] = 11 + 6 = 17

Lazy Propagation: Defer Until Asked

Point updates are O(log n). But range updates without lazy propagation are not. If you add 5 to every element in [0, n/2], a naive approach visits every leaf in that range: O(n). With n such updates, O(n²). That breaks everything.

Lazy propagation defers updates. Apply the change to a node's aggregate immediately, but do not push it to children until you actually need to visit them. Procrastination, formalized as a correctness invariant.

Each node gets a second value: lazy[node]. This holds a pending delta that has been applied to tree[node] but not yet propagated to the children.

Initial: arr=[3,1,4,1,5], tree built normally

range_update(+5 to [0..2]):
  node 1 [0..4]: partial, recurse
    node 2 [0..2]: fully covered.
      tree[2] += 5 * 3 = +15  -> tree[2] = 23
      lazy[2] += 5
      STOP. Do not touch children 4 and 5 yet.
    node 3 [3..4]: outside [0..2], skip
  tree[1] = tree[2] + tree[3] = 23 + 6 = 29

Lazy state: lazy[2] = 5 (children 4,5 haven't been updated)

When you later need to descend into a node's children, you push down first:

def _push_down(self, node: int, start: int, end: int) -> None:
    if self.lazy[node] == 0:
        return
    mid = (start + end) // 2
    left, right = 2 * node, 2 * node + 1
    # Apply the pending delta to children's aggregates
    self.tree[left]  += self.lazy[node] * (mid - start + 1)
    self.tree[right] += self.lazy[node] * (end - mid)
    # Pass the lazy down
    self.lazy[left]  += self.lazy[node]
    self.lazy[right] += self.lazy[node]
    self.lazy[node] = 0

The update and query functions call _push_down before recursing into children. The key invariant: tree[node] is always the correct aggregate for its segment, but lazy[node] is a pending delta that has been counted in tree[node] but not yet passed to tree[2*node] or tree[2*node+1].

The amber node (index 2) is the lazy boundary. tree[2]=23 is correct for its full range. lazy[2]=5 is a promise to its children that hasn't been cashed yet. The dashed red nodes hold stale values until something descends through them.

The Classic Lazy Bug

The bug is forgetting to push down before querying, not just before updating.

People remember to push down in the update path (because you need accurate children to recompute the parent). They forget it in the query path. The query descends into a child, reads a stale value because a lazy delta sitting in an ancestor was never pushed down to it, and returns a wrong number. Most queries still pass. Only queries that partially overlap a node with an outstanding lazy fail, and the failure is nondeterministic depending on query order. This is the kind of bug you debug for two hours convinced the language's integer arithmetic is broken, then find a missing _push_down call and feel a complicated mix of relief and shame.

The complexity doesn't change. The four-nodes-per-level argument holds for lazy operations exactly as for plain queries: at most four nodes per level, O(1) per push-down, O(log n) levels. Every operation stays O(log n).

Core Operations at a Glance

The O(n) lazy array is unavoidable: every node can hold a pending update simultaneously. In practice it is just one extra integer per node alongside the tree value.

One Structure, Every Language

All implementations below build a range sum segment tree with point update and range query. Nodes are 1-indexed (root at index 1, children of i at 2i and 2i+1). The input array is 0-indexed.

class SegmentTree:
    def __init__(self, arr: list[int]) -> None:
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self._build(arr, 1, 0, self.n - 1)

    def _build(self, arr: list[int], node: int, start: int, end: int) -> None:
        if start == end:
            self.tree[node] = arr[start]
            return
        mid = (start + end) // 2
        self._build(arr, 2 * node, start, mid)
        self._build(arr, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def update(self, index: int, value: int) -> None:
        self._update(1, 0, self.n - 1, index, value)

    def _update(self, node: int, start: int, end: int, index: int, value: int) -> None:
        if start == end:
            self.tree[node] = value
            return
        mid = (start + end) // 2
        if index <= mid:
            self._update(2 * node, start, mid, index, value)
        else:
            self._update(2 * node + 1, mid + 1, end, index, value)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, left: int, right: int) -> int:
        return self._query(1, 0, self.n - 1, left, right)

    def _query(self, node: int, start: int, end: int, left: int, right: int) -> int:
        if right < start or end < left:
            return 0
        if left <= start and end <= right:
            return self.tree[node]
        mid = (start + end) // 2
        return (self._query(2 * node, start, mid, left, right) +
                self._query(2 * node + 1, mid + 1, end, left, right))

What Problems Segment Trees Solve

Segment trees are the right tool for a specific shape of problem: a sequence of elements with repeated queries over contiguous ranges, where the elements also change over time.

Aggregate range queries on mutable data. Range sum (LeetCode 307), range minimum (RMQ), range maximum, range GCD, range XOR. If the aggregate function is associative (you can split the segment at any point and combine sub-results), a segment tree handles it.

Range updates. Add delta to all elements in [l, r], set all elements in [l, r] to a value. With lazy propagation, both are O(log n).

Non-invertible aggregates. Fenwick trees (BIT) handle prefix sums but require the operation to be invertible (you compute prefix[r] - prefix[l-1]). Min and max are not invertible. Segment trees handle them without issue.

Coordinate compression problems. When processing events in sorted order, you often want to count or query a range in a "compressed" domain. Segment trees work over the compressed indices.

Persistent and 2D variants. Persistent segment trees (create a new version on every update, O(log n) new nodes per version) support point-in-time queries. 2D segment trees handle rectangle queries and updates.

Spotting the Pattern

Three signals that a problem wants a segment tree:

1. The problem gives you an array and asks for a function over a range [l, r]: sum, min, max, count of elements satisfying some property, etc.
2. The array changes. Queries and mutations are interleaved, so prefix sums rebuilt every time would be too slow.
3. The aggregate function is associative. You can split "sum of [l, r]" into "sum of [l, mid] + sum of [mid+1, r]" for any mid in range.

If all three hold, a segment tree almost certainly fits.

Worked Example 1: Range Sum Query, Mutable

Problem. You have an array of integers. Handle two operations: update(i, val) sets arr[i] = val, and sumRange(l, r) returns the sum of elements from index l to r inclusive. There are up to 3 * 10^4 operations and n up to 3 * 10^4. (LeetCode 307)

Why segment tree. The naive approach: store the array, sum in O(n) per query. That is O(n) per query * 3 * 10^4 queries = O(n²) total. Too slow. Prefix sums give O(1) query but O(n) rebuild on every update: same problem. Reach for a segment tree. Build once in O(n). Each subsequent operation is O(log n). Total: O(n + Q log n) where Q is the number of queries. Fits comfortably.

The merge function is addition. Node covers [l, r]: tree[node] = sum of arr[l..r]. Splitting by midpoint gives correct subtree sums. Point update propagates up the path. Range query returns the sum by combining full-coverage nodes.

Worked Example 2: Warehouse Stock Monitoring

Problem. You have n warehouses with initial stock levels. You receive two types of queries: restock(l, r, delta) adds delta units to every warehouse in [l, r], and min_stock(l, r) returns the minimum stock level in warehouses [l, r]. Both operations arrive in an interleaved stream of Q queries.

Why lazy segment tree. min_stock is a range minimum query, which a segment tree handles with tree[node] = min of arr[l..r] and merge function Math.min. The restock operation is a range update: add delta to every element in [l, r]. Without lazy propagation, this touches every leaf in [l, r]: O(n) per update. With lazy propagation: update only the O(log n) nodes that fully cover the range, store the pending delta in their lazy values, and push down when you later need to descend. Both operations are O(log n).

The key realization: min with range-add is a compatible pair for lazy propagation. If a node covering [l, r] has a pending delta d, the minimum over [l, r] increases by exactly d. So tree[node] += d is the correct immediate update, and lazy[node] += d records what to pass to children later. This combination works cleanly because adding a constant to all elements in a range shifts the minimum by exactly that constant.

The Recap

• A segment tree is a complete binary tree stored in a flat array of size 4n. Root at index 1, children of i at 2i and 2i+1.
• Build runs in O(n) because there are exactly 2n-1 nodes, each visited once with O(1) merge.
• Range queries run in O(log n) because at most four nodes are visited per tree level.
• Point updates run in O(log n): walk the root-to-leaf path of length O(log n), recompute each ancestor.
• Range updates need lazy propagation. Mark nodes as "dirty" when their segment is fully covered, push the pending change to children only when descending past them.
• The classic lazy bug: forgetting to push down before querying, not just before updating.
• Use segment trees when: aggregate queries over ranges, mutable data, and an associative merge function.
• Fenwick trees are simpler and faster for prefix-sum-only workloads. Use them there. Use segment trees when you need min, max, or range updates.

If you want to practice explaining these tradeoffs out loud under interview pressure, SpaceComplexity runs voice-based mock DSA interviews with rubric feedback on exactly this kind of problem. Talking through a segment tree build while an interviewer watches is a different skill from writing the code quietly.

Segment trees also pair naturally with other techniques: if your array is implicit (you do not need to store all n values, just answer queries), look into implicit (dynamic) segment trees built with pointers and on-demand node creation. If you need historical queries ("what was the range sum before the k-th update?"), persistent segment trees create O(log n) new nodes per update and answer point-in-time queries in O(log n) on any version.

The dynamic programming post covers another family of problems where the "build something over subproblems" pattern applies, and the sliding window post covers the simpler range techniques you should reach for before pulling out a segment tree.

Further Reading

• Segment Trees, cp-algorithms.com, the most thorough single-page reference, covers persistent and 2D variants
• Segment tree, Wikipedia, formal definitions and geometric origins
• Segment Tree, GeeksforGeeks, worked examples with diagrams for range min and lazy propagation
• Segment Trees, Algorithmica, cache-efficient layouts, bottom-up variants, SIMD approaches for high-performance implementations