Segment Tree Visualization | Range Sum, Point Update, Lazy Propagation

The idea: one sum for every range

You have an array and two kinds of request mixed together: "what is the sum of a[l..r]?" and "change some values". Adding the numbers one by one makes a query cost O(n). A table of prefix sums makes a query O(1), but then one change costs O(n) to repair. A segment tree makes both O(log n).

A segment tree over a = 5, 3, 7, 9, 6, 4, 1, 2. The root covers [0,7] with sum 37; its children cover [0,3] with 24 and [4,7] with 13; the next level holds [0,1] 8, [2,3] 16, [4,5] 10 and [6,7] 3; the leaves hold the eight array values. — Every node stores the sum of a range: the leaves are the array, each parent is left + right, and the root is the total.

The page uses a = [5, 3, 7, 9, 6, 4, 1, 2], so n = 8 and the tree is a perfect binary tree with 15 nodes on 4 levels. Each node covers a range [lo, hi]; its children cover the left half [lo, mid] and the right half [mid+1, hi], with mid = (lo + hi) / 2 rounded down.

Build

Build the tree bottom-up: a leaf copies a[i], and a parent is the sum of its two children. Every node is visited once, so building costs O(n) (Demo: build, leaves from the array, parent = left + right).

build(k, lo, hi):
    if lo == hi: sum[k] = a[lo]; return
    mid = (lo + hi) / 2
    build(2k, lo, mid); build(2k+1, mid+1, hi)
    sum[k] = sum[2k] + sum[2k+1]

Range-sum query: outside, inside, partly inside

Start at the root and look at each node's range against the query range [l, r]:

Outside (grey): no overlap, return 0 and do not go lower.
Inside (green): the node's whole range is in [l, r], so its stored sum is part of the answer. Stop here.
Partly inside (orange): ask both children and add their answers.

The query sum of a[2..6] on the same tree. The root, [0,3], [4,7] and [6,7] are partly inside; [0,1] and leaf 7 are outside; [2,3] with 16, [4,5] with 10 and leaf 6 with 1 are inside, giving 16 + 10 + 1 = 27. — sum a[2..6] = 16 + 10 + 1 = 27: three stored sums cover the five numbers exactly, and 9 of the 15 nodes are visited.

The green nodes never overlap and together cover [l, r] exactly (Demo: sum of a[2..6], three nodes cover it). On each level at most two nodes are partly inside (the ones holding l and r), so at most four nodes per level are visited and at most two are taken. That is O(log n) work; Demo: sum of a[1..6], four nodes, two per level takes 3 + 16 + 10 + 1 = 30.

Point update

To set a[i] = x, walk from the root to leaf i, set the leaf, and recompute each sum on the way back up. Only the nodes on that path contain index i, one per level: log₂ 8 + 1 = 4 nodes. The other 11 sums stay correct (Demo: set a[3] = 2, fix the sums on the path up: 9 → 2 at the leaf, then 16 → 9, 24 → 17 and the total 37 → 30).

Range add and lazy propagation

Adding v to every element of a[l..r] with point updates costs one path per element: O(n log n) in the worst case. Lazy propagation brings it back to O(log n). The walk is the same as a query, but when a node is inside the range:

its sum grows at once by v × (hi − lo + 1), because every element under it grows by v;
it keeps a lazy tag +v (yellow chip): "my children have not heard about this yet";
the walk stops there. A partly inside node recomputes sum = left + right on the way back up.

Demo: add +2 to a[2..7] with two lazy tags touches only 5 nodes: [2,3] becomes 16 + 2 × 2 = 20 with tag +2, [4,7] becomes 13 + 2 × 4 = 21 with tag +2, and the total becomes 49. Leaves 2 to 7 are now stale: the array row under the tree shows the real values, but the leaves still show the old ones.

A tag is pushed down only when a later query or update has to go below its node. Push gives each child sum += tag × its length and tag (if the child is not a leaf), then clears the parent's tag. The sums seen by a query are then correct again.

Before: node [4,7] has sum 21 and tag +2, its children [4,5] and [6,7] still have sums 10 and 3. After the push: [4,7] has sum 21 and no tag, [4,5] has sum 14 and tag +2, [6,7] has sum 7 and tag +2. — Pushing the tag on [4,7] down: each child adds 2 × its length (2) and takes the tag; the parent's sum does not change.

Demo: lazy push-down, add +2 to a[2..7] then sum a[5..6]: the query reaches [4,7], pushes its tag to [4,5] and [6,7], then pushes again from each of them to the leaves, and answers 6 + 3 = 9.

push(k):
    if tag[k] != 0:
        for c in (2k, 2k+1):
            sum[c] += tag[k] * len(c)
            if c is not a leaf: tag[c] += tag[k]
        tag[k] = 0

Cost compared

	Range sum	Point update	Range add	Memory
Plain array	O(n)	O(1)	O(n)	n
Prefix sums	O(1)	O(n)	O(n)	n + 1
Fenwick tree (binary indexed tree)	O(log n)	O(log n)	O(log n) with two trees	n
Segment tree	O(log n)	O(log n)	O(log n) with lazy tags	2n to 4n

A Fenwick tree is smaller and faster for sums, but it needs an operation that can be undone (subtraction). A segment tree works for any associative merge: min, max, gcd, "count of zeros", even matrix products. For range min with range add, the tag rule changes to min += tag (no × length).

Stored in an array

Like a binary heap, the tree needs no pointers: node k has children 2k and 2k + 1 and parent k / 2, with the root at 1. When n is not a power of two the tree is not perfect, and an array of size 4n is always enough. Compare the pointer-based binary search tree, which orders keys instead of covering ranges, and the skip list and B-tree, which also trade a little memory for O(log n) operations.

For the same operations on a Fenwick tree, side by side, see Segment Tree vs Fenwick Tree.

What the page leaves out

The page keeps n = 8 so all 15 nodes fit, and only sums. It leaves out other merge functions (min, max, gcd), range assign tags (which overwrite instead of add), the iterative bottom-up segment tree of size 2n, persistent segment trees that keep old versions, merge sort trees, 2D segment trees, segment trees over coordinates that are compressed first, and the Fenwick tree, which answers the same sums with less memory.