Segment tree (range query + point update)

37 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Six numbers on a line: 1, 3, 5, 7, 9, 11. Two kinds of request keep arriving: "what is the sum from position 1 to position 3?" and "change position 1 to 10". For a sum you add the numbers in the range, at most 6 additions. For a change you overwrite one number. Both are easy with six numbers.

Now make it a million numbers and a million requests. Adding up a range costs up to a million steps, so the sums alone could be a trillion steps. The prefix-sum trick (store running totals) makes every sum two lookups, but then one change forces every later running total to be rewritten, up to a million steps per change. Each shortcut fixes one request and ruins the other. We want both in a few steps.

Build the structure, one piece at a time

Piece one: a node that knows the sum of a range. Write the six numbers as leaves. Above each pair, write the pair's sum; above each pair of those, their sum; and so on up to one root that holds the sum of everything. Levels from the top:

Each node's range is split in the middle between its two children, so the tree has about log₂ n levels.

Piece two: answering a sum. For the range [1..3], start at the root. A node whose range lies entirely inside [1..3] is taken whole and not opened. A node entirely outside is ignored. A node that straddles the boundary is opened and the question is passed to both children. [0..2] straddles, so open it: [0..1] straddles, open it: leaf [0] is outside, leaf [1] is inside, take 3; [2..2] is inside, take 5. [3..5] straddles: [3..4] straddles: leaf [3] inside, take 7; leaf [4] outside; [5..5] outside. Total 3 + 5 + 7 = 15.

Piece three: a change. Set position 1 to 10. Overwrite the leaf, then walk up the single path of ancestors and recompute each from its two children: [0..1] = 1 + 10 = 11, [0..2] = 11 + 5 = 16, root = 16 + 27 = 43. Only three nodes changed. Asking [1..3] again now takes 10 + 5 + 7 = 22.

Why it is correct

The invariant is that every node holds the sum of its whole range. Building it from the leaves up makes it true. A change rewrites one leaf and then every ancestor of that leaf, in order from the bottom; each ancestor is recomputed from children that are already correct, so it becomes correct, and no other node's range contains the changed position, so no other node needs to change.

A query is correct because the nodes it takes whole are disjoint and together cover exactly the asked range: a straddling node is never taken, it is split, and the splitting continues until every piece is either fully inside or fully outside.

Why it is fast

A change touches one leaf and one node per level above it, so about log₂ n + 1 nodes: 21 for a million numbers, against a million for prefix sums.

A query visits at most four nodes per level. At each level, the nodes still being opened are only those that straddle one of the two boundaries of the asked range, and a boundary can be straddled by at most one node per level, since nodes at a level are disjoint. Each straddling node opens two children. So the work is at most 4 log₂ n node visits:

query ≤ 4 · log₂ n, update ≤ log₂ n + 1

Both are O(log n). The tree needs about 2n nodes of memory.

Sum is only one choice of what a node holds. Minimum, maximum, greatest common divisor, or a count all work, as long as a parent's value can be computed from its two children's values.

How to recognise it in an interview

Cues: a mix of "update one position" and "ask about a range" that repeats many times, or a range question asked over positions that are being filled in while you scan. Say: "updates and range queries both need to be fast, so I will use a segment tree with O(log n) for each".

Count of Smaller Numbers After Self scans from the right, keeping a segment tree over values: for each number, query how many smaller values have been inserted, then insert it. Longest Increasing Subsequence II keeps, over values, the best subsequence length ending at each value, and a range maximum over [v − k, v − 1] gives the best predecessor. My Calendar III stores bookings as range additions and asks for the maximum overlap, the root of a max tree with lazy range updates.

02The idea in one line

A binary tree of ranges; a query visits O(log n) nodes, an update climbs one path.

Reach for it when: Range sum query mutable, count of smaller after self, falling squares, my calendar III.

Cost: O(log n) per op.

03The walk-through, step by step

The video works one example: Range sum on [1,3,5,7,9,11], update index 1, query [1,3]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Each node stores the sum of its whole range; the root covers [0,5]
2. query [1,3]: descend; a node fully inside is taken whole
3. Taken nodes 3 + 5 + 7 = 15
4. update index 1 → 10: change the leaf
5. Climb: node [0,1] = 1 + 10 = 11
6. Climb: node [0,2] = 11 + 5 = 16
7. Climb: node [0,5] = 16 + 27 = 43
8. query [1,3] again: 3 + 5 + 7 = 15
9. Query touches O(log n) nodes; update climbs one path: O(log n) each

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Advanced Structures: Fenwick tree (binary indexed tree), Ordered set / sorted container, Bucketing by value range, Matrix exponentiation for recurrences, Meet in the middle.