Running totals answer a range sum at once but are slow to update. Here a tree of stretch sums does both quickly. Watch it answer one range.
Adding up any range quickly
Eight values in a tree of stretch sums, answering a range in a few nodes
void build(const int *a){ for (int i = 0; i < N; i++) tree[N + i] = a[i]; for (int i = N - 1; i >= 1; i--) tree[i] = tree[2 * i] + tree[2 * i + 1];} void update(int i, int value){ int p = N + i; tree[p] = value; for (p /= 2; p >= 1; p /= 2) tree[p] = tree[2 * p] + tree[2 * p + 1];} int query(int l, int r){ int s = 0; for (l += N, r += N; l < r; l /= 2, r /= 2) { if (l % 2 == 1) { s += tree[l]; l++; touched++; } if (r % 2 == 1) { r--; s += tree[r]; touched++; } } return s;} int main(void){ const int a[N] = { 5, 2, 7, 1, 4, 8, 3, 6 }; build(a); int s1 = query(L, R); printf("sum [%d, %d) = %d from %d nodes\n", L, R, s1, touched); update(3, 5); int s2 = query(L, R); printf("after a[3] = 5: sum [%d, %d) = %d, root %d\n", L, R, s2, tree[1]); return 0;main has started.
- sum
- –
- nodes
- –
- root
- –
Output
Describe this picture
The picture is a tree of numbers standing over a row of boxes. The row holds the eight values 5, 2, 7, 1, 4, 8, 3 and 6 with their indices 0 to 7. Each circle of the tree holds the sum of the values beneath it: the bottom circles are the values themselves, each one above it adds the two below, and the top circle adds all eight. Under the picture are the lines of segtree.c, with the line about to run marked, one sentence on the current step, three readouts (the sum so far, the nodes taken, and the root) and the output. Below them are two sliders, Range start l from 0 to 7 and Range end r from 1 to 8, which pick the range [l, r), the values from index l up to but not including r. The clip plays once, about 18 seconds, for the range [1, 7). First the tree grows from the bottom up: the eight leaves, then 7, 8, 12 and 9, then 15 and 21, then the root, 36. Then the query: the boxes 1 to 6 are toned, and at each level the circles still to cover are shaded. At the bottom it takes the 2 at the left end and the 3 at the right end; one level up it takes 8 and 12 whole; the four taken circles light, and 2 + 3 + 8 + 12 = 25. Next a[3] changes from 1 to 5: its leaf changes, then the circle above it, then the next, up to the root, which becomes 40, one path of four circles. The same range is summed again, 29, and the clip rests on the two lines of output. Moving a slider picks another range and plays again from the first query, so the build is not repeated; the range is kept in the page address as segtree.l and segtree.r, and a paused step as segtree.step.
A tree of stretch sums
A segment tree keeps, besides the values, the sum of each of a set of stretches. The whole array is one stretch; its two halves are two more; their halves are four more, down to the single values. Each stretch is a node of a binary tree, and a node’s sum is the sum of its two children’s.
For the eight values here:
| Level | Stretches | Sums |
|---|---|---|
| root | 0 to 7 | 36 |
| halves | 0 to 3, 4 to 7 | 15, 21 |
| quarters | 0 to 1, 2 to 3, 4 to 5, 6 to 7 | 7, 8, 12, 9 |
| leaves | each value | 5 2 7 1 4 8 3 6 |
Any range is a union of a few of these stretches. [1, 7), the values at 1 to 6, is the leaf 2, the stretch 2 to 3 (8), the stretch 4 to 5 (12) and the leaf 3: four nodes, 25. The query never visits the leaves inside a stretch it takes whole, so the number of nodes stays small however wide the range: over all 36 ranges of these eight values, a query takes one node 15 times, two nodes 14 times, three nodes 6 times, and four only for [1, 7).
The code and its cost
The tree in an array
static int tree[2 * N];The tree is stored in an array, with no pointers. The root is tree[1], and node i has its children at 2i and 2i + 1, its parent at i / 2. With n = 8, the leaves are tree[8] to tree[15], the values in order, and tree[0] is not used: 2n cells in all.
void build(const int *a)
{
for (int i = 0; i < N; i++)
tree[N + i] = a[i];
for (int i = N - 1; i >= 1; i--)
tree[i] = tree[2 * i] + tree[2 * i + 1];
}The leaves are copied first, then each parent from tree[7] down to tree[1] adds its children, which are always already done: n − 1 additions.
A range sum
int query(int l, int r)
{
int s = 0;
for (l += N, r += N; l < r; l /= 2, r /= 2) {
if (l % 2 == 1) {
s += tree[l];
l++;
touched++;
}
if (r % 2 == 1) {
r--;
s += tree[r];
touched++;
}
}
return s;
}The range is half open, [l, r): from l up to but not including r. The loop starts at the leaves and climbs both ends together. A left end that is a right child (odd) sticks out of its parent’s stretch, which also covers a value left of the range, so that node is taken alone and l steps past it. Likewise a right end at an odd r means the node just before it, tree[r - 1], sticks out on the right: take it and step r back. Then both ends move up a level, l /= 2 and r /= 2, and the loop stops when they meet. At most two nodes are taken per level, so a query takes at most about 2 log₂ n nodes.
In the clip, [1, 7) starts at l = 9 and r = 15, both odd: take tree[9] (2) and tree[14] (3). Then l = 5 and r = 7: take tree[5] (8, a[2] and a[3]) and tree[6] (12, a[4] and a[5]). Then l = r = 3, and the loop ends: 4 nodes, 25.
A query does not visit every leaf in the range. [0, 8) takes one node, the root.
An update
void update(int i, int value)
{
int p = N + i;
tree[p] = value;
for (p /= 2; p >= 1; p /= 2)
tree[p] = tree[2 * p] + tree[2 * p + 1];
}Only the nodes whose stretch contains a[i] change: its leaf and the leaf’s ancestors, one path of log₂ n + 1 cells. update(3, 5) writes tree[11] = 5, tree[5] = 12, tree[2] = 19 and tree[1] = 40. Prefix sums would have changed five totals; for a million values, they could change a million, where the tree changes 21 cells.
sum [1, 7) = 25 from 4 nodes
after a[3] = 5: sum [1, 7) = 29, root 40Other operations
Nothing in the tree depends on addition except that sums can be combined in any grouping. Any associative operation works the same way: store the minimum of each stretch and the query returns the minimum of a range; or the maximum, or the product. Only the line that combines two children, and the starting value of s, change.
Pending marks for ranges
Pending marks
Adding 10 to a range marks two nodes; a later sum passes a mark down only where it must
static void apply(int node, int lo, int hi, long x){ sum[node] += x * (hi - lo); pending[node] += x;} static void push_down(int node, int lo, int hi){ if (pending[node] != 0) { int mid = lo + (hi - lo) / 2; apply(2 * node, lo, mid, pending[node]); apply(2 * node + 1, mid, hi, pending[node]); pending[node] = 0; }} void range_add(int node, int lo, int hi, int l, int r, long x){ if (r <= lo || hi <= l) return; if (l <= lo && hi <= r) { apply(node, lo, hi, x); return; } push_down(node, lo, hi); int mid = lo + (hi - lo) / 2; range_add(2 * node, lo, mid, l, r, x); range_add(2 * node + 1, mid, hi, l, r, x); sum[node] = sum[2 * node] + sum[2 * node + 1];} long range_sum(int node, int lo, int hi, int l, int r){ if (r <= lo || hi <= l) return 0; if (l <= lo && hi <= r) return sum[node]; push_down(node, lo, hi); int mid = lo + (hi - lo) / 2; long s1 = range_sum(2 * node, lo, mid, l, r); long s2 = range_sum(2 * node + 1, mid, hi, l, r); return s1 + s2;}int main(void){ const int a[N] = { 5, 2, 7, 1, 4, 8, 3, 6 }; build(a, 1, 0, N); range_add(1, 0, N, 2, 6, 10); long whole = range_sum(1, 0, N, 0, N); long right = range_sum(1, 0, N, 5, 8); printf("after adding 10 to [2, 6): sum [0, 8) = %ld, sum [5, 8) = %ld\n", whole, right); return 0;}main has started.
- pending marks
- 0
- whole
- –
- right
- –
Output
Describe this picture
The picture shows the same eight values in a segment tree drawn the other way: node 1 covers [0, 8), and each node’s two children cover its two halves, down to the eight leaves. The sum of each node is inside its circle. A number such as +10 under a circle is a pending mark: an amount that has been added to the node’s sum but not yet to the nodes below it. Beside the tree, or below it on a narrow screen, the calls that are running are cards, main at the top and each call under its caller, titled with the node and its stretch. On the tree the node of the innermost call is ringed and the nodes of the calls above it are shaded; the node that apply or push_down is working on is drawn in the accent colour. Under the picture are the lines of lazy.c, the line about to run marked, one sentence on the current step, three readouts (the pending marks in the tree, and the two sums once computed) and the output. The replay lasts about 24 seconds. The tree is built, with 36 at the root. Then range_add adds 10 to every value in [2, 6). It goes down from the root; node 5, [2, 4), and node 6, [4, 6), lie inside the range, so each gets 20 added to its sum and a mark of +10, and the calls return without going lower; on the way back the root becomes 76. The sum of [0, 8) reads the root, 76, at once. The sum of [5, 8) goes down to node 6, which is only partly inside, so node 6 first passes its mark down: its two leaves get +10 each, 14 and 18, and node 6’s mark goes. The call then takes 18 from the leaf for [5, 6) and 9 from node 7, and the sum is 27. The replay rests on the output. The transport plays and pauses, steps, and scrubs; a paused step is kept in the page address as lazy.step.
Adding x to every value in a range one value at a time would rewrite every leaf in it and all their ancestors. Instead, lazy.c stops at the nodes whose stretch lies wholly inside the range, as a query does, and leaves a pending mark on each:
static void apply(int node, int lo, int hi, long x)
{
sum[node] += x * (hi - lo);
pending[node] += x;
}The node’s sum is right at once, since all hi − lo values under it grew by x; the values below have not been told. A later call that needs a node’s children first passes the mark down:
static void push_down(int node, int lo, int hi)
{
if (pending[node] != 0) {
int mid = lo + (hi - lo) / 2;
apply(2 * node, lo, mid, pending[node]);
apply(2 * node + 1, mid, hi, pending[node]);
pending[node] = 0;
}
}This is lazy propagation: a range update marks at most about 2 log₂ n nodes, and a mark moves down one level only when a later call has to look below it. In the replay the sum of [0, 8) needs nothing below the root, so no mark moves; the sum of [5, 8) needs inside node 6, so its mark moves to its children, and node 5’s mark stays where it is.
This version is recursive: each call covers a stretch [lo, hi) and calls itself on the two halves. It uses up to 4n cells, the usual safe size for a recursive segment tree whose n is not a power of two.
Running it yourself
gcc -std=c11 -Wall -Wextra -pedantic segtree.c -o segtree
./segtree
gcc -std=c11 -Wall -Wextra -pedantic -DL=2 -DR=6 segtree.c -o segtree
./segtree
gcc -std=c11 -Wall -Wextra -pedantic lazy.c -o lazy
./lazyWorked example
The whole array. Query [0, 8): l = 8 and r = 16 are both even, and so are 4 and 8, and 2 and 4; at 1 and 2, l is odd: take tree[1], 36. One node.
[2, 6) by hand. l = 10 and r = 14 are even: nothing taken; up to l = 5 and r = 7, both odd: take tree[5] (8) and tree[6] (12). Then l = r = 3. Sum 20, from 2 nodes.
Which stretch does tree[6] cover? Its children are tree[12] and tree[13], the leaves of a[4] and a[5].
Cells rewritten by an update when n = 16. The leaf and its four ancestors: 5, log₂ 16 + 1.
A million values. log₂ of a million is about 20. A query takes at most about 40 nodes, and an update rewrites 21 cells, a leaf and 20 ancestors, against prefix sums’ update of up to a million totals.
Where it’s used
Changing data. Running scores, stock levels and windows of sensor readings change all the time and are queried by range; a segment tree keeps both quick.
Computational geometry. Sweeps over rectangles and intervals keep counts or lengths along a line in a segment tree.
Scheduling. Bookings over time intervals add load to a range of time slots and ask for the largest load in a range, with pending marks for the range updates.
Reference card
| Code or idea | Meaning |
|---|---|
tree[1]; children 2i and 2i + 1 | the root, and node i’s two halves |
tree[N + i] | the leaf of a[i]; 2n cells in all |
| build | parents from n − 1 down to 1: n − 1 additions |
| query [l, r) | climb from both ends, taking a node that sticks out: at most about 2 log₂ n nodes |
| update | a leaf and its ancestors: log₂ n + 1 cells |
| any associative operation | sum, minimum, maximum, product |
| pending mark | added to a node, not yet to its children |
| push_down | pass a node’s mark to its children when they are needed |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, long 8, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.