Point updates and a bottom-up min tree

Why it matters

Updates are the reason to choose a segment tree over prefix sums. Prefix sums rebuild many cells after every change. A segment tree changes only the nodes on one path from a leaf to the root, which is about log n nodes. This lesson shows that update, and it shows a second, shorter form of the tree that many competitive programmers prefer for minimum and maximum queries. Both forms give O(log n) for queries and updates, and knowing both is what lets you pick the one that fits the problem.

What a point update is

A point update changes one element of the array: a[pos] = val. The word "point" means one position, as opposed to a range update that changes a whole run of positions. Lesson 4 handles ranges. Here we change one value at a time.

Think about a sports tournament bracket. Each match is a node, the final is the root, and the first-round pairs are the leaves. If one player's score changes after the semifinal, you do not replay the whole tournament. You replay only the matches on the path from that player's first match up to the final. Every other match stays as it was. A segment tree update works the same way.

The update has two phases. First it walks down from the root to the leaf for pos, choosing the left or right child at each level. Second it walks back up, recomputing each node from its two children. Going down finds the leaf. Coming back up repairs every stored answer that the leaf's change touched. Both phases follow one path, so the cost is the path length, which is about log2 n.

The recursive update

Here is the update for the sum tree from the last lesson. It is a function that calls itself, like the query. The base case is a leaf, where it stores the new value. The recursive case goes to the child that contains pos, then recomputes the current node.

void update(int node, int l, int r, int pos, long long val) {
    if (l == r) { t[node] = val; return; }
    int mid = (l + r) / 2;
    if (pos <= mid) update(2 * node, l, mid, pos, val);
    else update(2 * node + 1, mid + 1, r, pos, val);
    t[node] = t[2 * node] + t[2 * node + 1];   // recompute on the way back up
}

The rule for choosing a child is the same split used in the build. If pos is at most mid, the position lives in the left child, which covers [l, mid]. Otherwise it lives in the right child, which covers [mid + 1, r]. Using pos <= mid in one place and pos < mid in another is a common error. The split must match exactly what the build did.

The line after the if is the important one. The recursive call returns after the child has been updated, so the child's stored answer is now correct. The parent's answer depends on it, so the parent must be recomputed before the call returns. The recompute happens once per level on the way back up, and that is what keeps every ancestor in step with the leaf.

Let us follow an update on the tree for {2, 4, 1, 7}. The call update(1, 0, 3, 2, 10) goes to node 3, which covers [2, 3], then to node 6, which covers [2, 2] and is a leaf. Node 6 becomes 10. Back at node 3 the recompute gives 10 + 7 = 17. Back at the root the recompute gives 6 + 17 = 23. Nodes 2, 4, 5 and 7 are not visited, and their values stay the same. The tree dump becomes 23 6 17 2 4 10 7 in slot order.

The segment tree after setting the third element to 10. The root becomes 23, node 3 becomes 17, and the leaf becomes 10. The highlighted path is 1, 3 and 6.

Worked example 1: a sum tree with commands

The next program answers a list of commands. A line q l r asks for a sum. A line u i v sets one element to v. The program is a complete sum tree with a point update, so you can watch both operations working on the same stored tree.

Input, one item per line:

4
2 4 1 7
4
q 0 3
u 2 10
q 0 3
q 1 3

Expected output:

14
23
21

Trace the four commands. The first q 0 3 is the whole array, so the root answers 14 at once. The command u 2 10 changes index 2 from 1 to 10, following the path we traced above: leaf 6, then node 3, then the root. The second q 0 3 now reads the root, which is 23, and the array is {2, 4, 10, 7}, with total 23. The last command q 1 3 covers indexes 1 to 3. That is the leaf for 4, plus node 3 which now holds 17. The answer is 4 + 17 = 21.

Notice what the update did not need. It did not rebuild the tree, and it did not touch the leaves for 2, 4 and 7. Those stored answers were already right. The update changed three nodes, and everything else was reused.

The iterative min tree

The recursive form is clear, but it uses function calls for every node. There is a shorter form, sometimes called a bottom-up or iterative segment tree. It stores the leaves in one block at the end of the array and builds the internal nodes with a simple loop. It needs only 2n slots, and the query is a plain loop with no recursion. It is the version most experienced programmers reach for when the operation is minimum or maximum.

The layout is different. The leaves are stored at positions n to 2n - 1. The leaf for element i is at position n + i. Every other position i from 1 to n - 1 is an internal node, built from its children 2i and 2i + 1. For n = 6, the leaves are at positions 6 to 11, and the internal nodes are at positions 1 to 5. Position 0 is not used.

Here is the layout for {5, 2, 8, 6, 3, 7}. Position 6 holds 5, position 7 holds 2, and so on up to position 11, which holds 7. Position 5 is built from positions 10 and 11, which hold 3 and 7, so it stores 3. Position 1 is the root, which covers the whole array in a way that the loop makes correct even though 6 is not a power of two.

Why does this work when the length is not a power of two? The reason is that minimum is both associative and commutative. Commutative means the order of the two arguments does not matter. Because min does not care about order, the tree can combine pieces in any grouping, and the query loop below can gather pieces from both ends without caring which piece came first. Sums are commutative too, so the same layout works for sums. Operations like string concatenation are associative but not commutative, and they need a more careful layout.

The build is a short loop. Copy the leaves in, then fill the internal nodes from the last one down to 1, so that each node's children are ready before the node is computed.

MinTree(const vector<int>& a) : n(a.size()), t(2 * a.size()) {
    for (int i = 0; i < n; i++) t[n + i] = a[i];
    for (int i = n - 1; i >= 1; i--) t[i] = min(t[2 * i], t[2 * i + 1]);
}

The loop runs from n - 1 down to 1. If it ran upward, node 1 would be computed before its children, and it would read values that have not been filled in yet. Going downward is what makes the order safe.

The iterative point update

The update starts at the leaf and walks up. There is no need to choose a left or right child, because the leaf's position in the array tells you where it is. Each parent is just pos / 2.

void update(int pos, int val) {
    pos += n;
    t[pos] = val;
    for (pos /= 2; pos >= 1; pos /= 2) t[pos] = min(t[2 * pos], t[2 * pos + 1]);
}

The first line moves from the element index to the leaf position. The second line stores the new value. The loop then recomputes each parent, one level at a time, until it reaches position 1. The loop runs about log2 n times. Forgetting the loop is the most common bug, and the debugging walkthrough later in this lesson shows what it does.

The iterative query

The query is the most unusual part, so take it slowly. The query covers the inclusive range [l, r]. The loop uses two moving positions: l starts at the leaf for the left end, and r starts one past the leaf for the right end. This half-open convention, where r is one past the end, makes the loop easy to write.

int query(int l, int r) const {        // both ends inclusive
    int res = INT_MAX;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
        if (l & 1) res = min(res, t[l++]);
        if (r & 1) res = min(res, t[--r]);
    }
    return res;
}

Each step looks at the two moving positions. If l is odd, it is a right child, so its node covers only what it covers, and nothing above it. The loop takes that node into the answer and steps l to the right with l++. If r is odd, the node just to its left is a left child that is inside the range, so the loop takes t[--r]. After handling the ends, both positions move up one level with / 2. The loop stops when l and r meet, which means no nodes are left to take.

Trace query(0, 5) on {5, 2, 8, 6, 3, 7}. Here l starts at 6 and r at 12. The positions are even, so nothing is taken, and both move up: l becomes 3 and r becomes 6. Now l = 3 is odd, so the loop takes t[3], which is the minimum of positions 6 and 7 (5 and 2), so it is 2, and moves l to 4. Then r = 6 is even. Both move up: l becomes 2 and r becomes 3. Now r = 3 is odd, so the loop takes t[2], which covers positions 4 and 5. The answer is the minimum of 2 and that node's value, and it stops. The program prints 2, which is the smallest of all six values.

Trace one more, query(2, 5). Here l = 8 and r = 12. Both are even, so both move up to l = 4 and r = 6. Both are even again, so they move to l = 2 and r = 3. Now l = 2 is even, so nothing is taken from the left. r = 3 is odd, so the loop takes t[2], which covers the leaves for indexes 2 to 5. The answer is 3, the smallest of 8, 6, 3 and 7. The loop did about log2 n steps, not n.

Worked example 2: an iterative min tree with commands

The program below uses the same command format as the sum example, but it uses the iterative min tree. The commands are q l r for a minimum and u i v for an update. Type the input into the Input box and run it.

Input, one item per line:

6
5 2 8 6 3 7
6
q 0 5
q 2 3
q 2 5
u 1 9
q 0 5
q 0 2

Expected output:

2
6
3
3
5

The first three answers are the traces from the last section: 2 for the whole array, 6 for indexes 2 and 3 (the minimum of 8 and 6), and 3 for indexes 2 to 5. The command u 1 9 changes index 1 from 2 to 9. Now the array is {5, 9, 8, 6, 3, 7}. The minimum of the whole array is 3, and the minimum of indexes 0 to 2 is 5. The fifth and sixth answers are those values, and they show that the update reached the tree: before the update, the minimum of indexes 0 to 2 was 2.

Worked example 3: a stress test with a random generator

How do you know a tree is correct on inputs you did not think of? The answer is the brute-force check from the last lesson, run on many random inputs. The program below does that for the min tree. It needs random numbers, and it needs them to be the same every time you run it, so that a bug can be reproduced. The trick is a linear congruential generator, a short formula that turns one number into the next. The formula is seed = seed * 1103515245 + 12345, using unsigned arithmetic so the number wraps around cleanly. The program then takes the high bits, which are more random than the low bits, and reduces them to a value from 0 to 99.

The program applies 300 random steps. Each step is either an update to a random position with a random value, or a query over a random range. Every query is also answered by a loop, and the two answers are compared.

Input, one item per line:

42

Expected output:

checks 152 mismatches 0

Read the program as a machine for creating tests. The seed is the only input, so the same seed always makes the same 300 steps. Change the seed to 7 and you get a different run, still reproducible. Zero mismatches means the tree agreed with the loop on all 152 queries. That is strong evidence, though not proof, because the test covers only the sequences the generator happened to make. A good habit is to run several seeds, and to keep any seed that found a bug, so that the bug stays fixed.

Notice what the program checks. It does updates and queries mixed together, which is the situation the tree is for. A test that only queries after one build would miss every bug in the update path.

Worked example 4: which parents change

Sometimes the clearest way to understand an update is to print the path it takes. The next program is a bottom-up sum tree. It reads the array, sets one leaf, and prints each parent position as it recomputes it. It also prints the total at the root.

Input, one item per line:

8
5 2 8 6 3 7 4 1
5 10

Expected output:

leaf 13 set to 10
recompute: 6 3 1
total 39

The leaf for index 5 is at position 8 + 5 = 13. Its parent is 6, then 3, then 1, which is the root. So the update touched three parents, which is log2 8 = 3. The total goes from 36 to 39, because index 5 changed from 7 to 10, and the root holds the sum of everything. The program shows the path, and the Viz below walks the same kind of tree top-down, so you can see the shape the path climbs.

For a larger array the path is longer by one step each time the size doubles. For 8 leaves there are 3 parents, for 16 there are 4, and for 1000000 there are about 20. That growth is what makes the update O(log n).

What happens inside: the cost of one update

Count the work in an update. The loop visits one position per level, and there are about log2 n levels. Each visit reads two children and writes one parent. So an update does a fixed amount of work per level, multiplied by the number of levels, which gives O(log n).

The memory access pattern is also friendly. The parents are at positions pos / 2, pos / 4 and so on. The array is contiguous, so the upper levels, which the loop reads often, stay in the processor's cache after the first few updates. Each update touches only a few cache lines, not the whole structure.

Compare that with the prefix table from the last module. Changing one value there rewrote every cell after it, which is up to n writes spread across the array. The segment tree does log n writes, and that is the difference that matters when n is a million.

A second trace of the bottom-up query

The first trace of the iterative query used ranges that start at an even position. The second one shows an odd left end and a boundary that crosses a level. Use the tree for {5, 2, 8, 6, 3, 7} again. The query is query(1, 4), which covers the values 2, 8, 6 and 3, so the answer should be 2.

Start with l = 1 + 6 = 7 and r = 4 + 6 + 1 = 11. The leaf at position 7 holds 2, and the leaf at position 10 holds 3. Position 7 is odd, so the loop takes t[7] = 2 and moves l to 8. Position 11 is odd, so the loop moves r to 10 and takes t[10] = 3. Now l = 8 and r = 10. Both move up one level: l becomes 4 and r becomes 5. Position 4 is even, so nothing is taken from the left. Position 5 is odd, so the loop moves r to 4 and takes t[4], which holds the minimum of positions 8 and 9, that is min(8, 6) = 6. Now l = 2 and r = 2, so the loop stops. The taken values are 2, 3 and 6, and the answer is 2.

Notice that the loop never looked at the root. The pieces it took were a leaf, another leaf, and one internal node, and together they covered the four indexes exactly once each. That exactness is the property to check: no index is taken twice, and none is missed. The stress test in worked example 3 checks it on hundreds of ranges, and that is a far better test than reading the loop by eye.

Recursive versus iterative: a comparison

The two trees you have seen solve the same problem in two shapes. The table below puts them side by side, so you can choose on purpose rather than by habit.

The recursive tree is easier to extend. Lazy propagation, range updates and "find the first position where the sum passes a value" are all natural in the recursive form, because the walk goes top-down and can push tags on the way. The iterative tree is shorter, uses less memory and has no function-call overhead. For a point-update minimum or sum, it is usually the better choice in competitive code.

The commutativity row matters for correctness, not just speed. The bottom-up layout for a non-power-of-two size can combine pieces in an order that does not match the array's left-to-right order. For minimum and sum that does not matter, because the order of combining does not change the answer. For operations like string concatenation or matrix multiplication it does, and you would use the recursive form or a power-of-two size instead.

Where point updates show up

Point updates are the common case in many real systems. A stock system changes one product's count when one item is sold. A scoreboard changes one team's score when one goal is scored. A thermostat log replaces one reading when a sensor is recalibrated. In each case the change is small, and the question that follows is often about a range: the total stock across a warehouse section, or the lowest score in a group of teams. The point update plus the range query is the pattern this lesson builds.

Think about how the costs add up over a day. Suppose a shop has 100000 products on its shelves and 50000 sales arrive in one hour, each one a point update, with 5000 range questions in between. A rebuild after each sale would cost 50000 times 100000, which is five billion writes, and nobody could wait for that answer. A segment tree costs 50000 updates of about 17 steps each, which is under a million steps, plus 5000 queries of about 34 steps each. The whole hour finishes in a fraction of a second. The difference is not a small tuning gain. It is the difference between a system that works and one that cannot keep up.

There is a subtle point about when the update happens. An update must be applied before the next query that could see it, not just eventually. A common design is a queue of updates applied in batches, and that is safe only if every query first flushes the queue. Forgetting the flush gives answers that lag behind the data, and that bug can hide for a long time, because the answers look plausible.

Finally, consider the order of events. The same set of updates and queries, given in a different order, gives different answers, and a tree must follow the order exactly. The command programs in this lesson read the events in order and answer each query at its position, which is the behaviour a correct system needs. The stress test in worked example 3 checks that order on random sequences, so a bug that depends on the order shows up there.

Common mistakes

Forgetting to recompute the parents. The update changes the leaf but not the nodes above it. Queries that read those nodes return stale values, and the program prints wrong answers with no error message at all. The debugging walkthrough below shows a real example.

Using < instead of <= at the midpoint. The recursive update must go left when pos <= mid. If it goes left only when pos < mid, the element at mid goes to the right child, which does not cover it, and the wrong leaf is changed.

Mixing inclusive and half-open ends. The iterative query takes [l, r] inclusive, but the loop works on r + 1. If you write r + n instead of r + n + 1, the element at r is left out of every query. Small tests can still pass by luck, so compare against a loop on many ranges.

Mixing the two layouts. The iterative tree stores leaves at n to 2n - 1 and the root at 1. The recursive tree stores leaves wherever its recursion puts them, and the root is also 1, but the leaf numbers are different. Using the iterative update on a recursive tree, or the reverse, writes to the wrong slots.

Building the internal nodes in the wrong order. The build loop must go from n - 1 down to 1. A loop that goes up uses children that do not exist yet.

Forgetting the offset. The update must add n to the position before it writes. Without pos += n, the write goes to a slot in the internal part of the array, and the root is corrupted.

Debugging walkthrough: a min tree that answers too early

A learner writes the min tree above, and the first queries are right. The learner then adds an update and tests it. The array is {5, 2, 8, 6, 3, 7}. The learner runs u 1 9 and then q 0 2. The correct answer is 5, the minimum of 5, 9 and 8. The program prints 2, which is the old value at index 1. The learner's update code is missing the recompute loop:

void update(int pos, int val) {
    pos += n;
    t[pos] = val;
    // the recompute loop was deleted while testing
}

Here is what happens. The leaf for index 1 is at position 7, and it is set to 9. The parents of position 7 are 3 and 1, but they are never recomputed, so they still hold the values from the build. Position 3 covers positions 6 and 7, which hold 5 and 9 now, but position 3 still holds 2, the old minimum of 5 and 2 at build time.

The query for [0, 2] uses position 8, which is 8, and position 3, which is still stale at 2. So the answer is 2. You can see the cause by printing the tree after the update. The leaf is 9, but its parent still says 2. The fix is the loop that recomputes the parents. With it restored, position 3 becomes min(5, 9) = 5, and the query returns 5.

The general lesson: when a query is wrong after an update, print the leaf you changed and its parents. If a parent disagrees with its children, the recompute step is missing or aimed at the wrong positions.

Variations and edge cases

A single-element array is a good test. With n = 1 the leaf is at position 1, which is also the root. The build loop does nothing, the update sets position 1 and the recompute loop starts at 0, so it does nothing, and the query [0, 0] returns the value. Check that all three operations work.

An array of length 6, 7 or 10 tests the non-power-of-two layout. Compare the answers with a loop for every range, as the stress test does.

A maximum tree uses the same code with max in place of min, and the neutral value INT_MIN in place of INT_MAX.

A sum tree uses + and the neutral value 0. The update and the query have the same shape, but the recompute uses +.

Updates that set a value to the same value it already had are allowed. The program still recomputes the path, and the result is correct.

Interview-style questions

"How do you update one element of a range structure in O(log n)?" Answer: walk the path from the leaf to the root and recompute each node from its two children. The path has about log n nodes, and every other node keeps its stored answer.

"Why does the iterative tree work for any array length?" Answer: the combining operation is associative and commutative, so the grouping of the pieces does not depend on the length being a power of two, and the query loop picks up the right pieces from both ends.

"What is the cost of building the tree?" Answer: O(n). Each internal node is computed once, and there are about n of them.

"Why is the iterative form faster in practice?" Answer: it uses a plain loop with no function calls, it uses 2n memory instead of 4n, and its upper levels stay in the cache.

Practice

1. Turn the iterative MinTree into a sum tree. Name the three lines you change. What neutral value does the query use?
2. After update(0, 1) on the example array {5, 2, 8, 6, 3, 7}, what do query(0, 5) and query(0, 0) print? Work them out by hand, then check with the program.
3. Add a method int get(int pos) const to the iterative tree that returns the current value of one element. Explain why it needs no loop.
4. Explain why the update loop uses pos /= 2 and not pos = pos - 1. Give the parent of position 9 and of position 10.
5. Write the recursive update for a min tree. Which line changes compared with the sum version?
6. For n = 5, list the leaf positions and the internal positions of the iterative tree. Which positions are never used?
7. In the sum command program from worked example 1, the array is {4, 4, 4, 4}. The commands are u 3 1 and then q 0 3. What does the query print? Work it out, then check with the program.
8. A learner's query uses r + n instead of r + n + 1. Give a small array and a query on which the answer is wrong, and explain why.
9. Explain why the build loop must go from n - 1 down to 1, and not upward.
10. Describe, in plain words for a teammate, why one update is O(log n) and not O(n). Use the tournament picture if it helps.

What you now know

• A point update walks one path, from the leaf to the root, and recomputes each node on the way.
• The recursive update goes left when pos <= mid and recomputes on the way back up.
• The iterative tree stores leaves at n to 2n - 1, builds parents from the bottom up, and needs only 2n slots.
• The iterative query takes l and r from both ends, takes odd nodes, and stops when they meet.
• Forgetting the recompute loop gives wrong answers with no error, so print the path when a query looks wrong.
• Use a seeded random generator and a brute-force check to test many mixed updates and queries.