Point updates and minimum queries in Python

Why it matters

A segment tree beats prefix sums because it handles changes cheaply. The point update is the first place you see that benefit. It is also a good way to learn the second big lesson of this module, which is that the same tree works for many operations. Switching from sums to minimums is a common interview variation, and it changes only two small things in the code.

This lesson has four parts. You will update one item and watch the path of nodes that change. You will turn the sum tree into a minimum tree and answer range minimum queries. You will write one generic tree that takes the operation as a function. Finally, you will use the minimum tree to search for the first item that is small enough, a pattern that appears often in interviews.

Point updates in plain words

A point update changes one item. In code it is a[i] = value. The item is a single point, not a range, which is why the name fits. The question is what happens to the tree.

Think back to the sales example from the first lesson. One salesperson changes their number. Their team total changes, then their department total, then the company total. No other team or department needs to change, because they do not contain that salesperson. The update only touches the totals above the person.

The same is true of the tree. Only the nodes whose segment contains index i can change. Those nodes form one path, from the root down to the leaf for i. A node whose segment does not contain i keeps its old value, because none of its items changed. So the update walks down one path, changes the leaf, and then recomputes each node on the way back up.

The steps for _update(node, l, r, i, value) are these. If l equals r, this node is the leaf for i, so store the new value. Otherwise compute mid. If i is at most mid, the leaf is in the left half, so recurse left. Otherwise recurse right. When the recursion returns, recompute the current node from its two children.

The path has one node per level, and the height of the tree is about log2(n). So the update costs O(log n). Compare that with prefix sums, where one change rewrites up to n values. That gap is the reason the segment tree exists.

Watching an update

The best way to understand the path is to watch it. The next program builds a sum tree for [1, 3, 5, 7, 9, 11], then changes index 1 from 3 to 10. The update method prints each node as it recomputes that node on the way back up.

The output is:

node 9 [1..1] now 10
node 4 [0..1] now 11
node 2 [0..2] now 16
node 1 [0..5] now 43
total = 43

The first line is the leaf for index 1. Its value changed from 3 to 10. The second line is its parent, [0..1], which is now 1 + 10 = 11. The third line is [0..2], now 11 + 5 = 16. The last line is the root, now 16 + 27 = 43. Only four nodes changed. The node for [3..5], with sum 27, was not on the path, so it was not printed and not touched.

Notice the order. The leaf prints first because the recursion reaches it first, then the parents print as the calls return. The update does its work on the way down (choosing the child) and on the way back up (recomputing the parent). Both halves are needed. If you forget the way back up, the leaf changes but its parents keep the old sums, and every later query on those parents is wrong.

The update method without the two print lines is short:

def _update(self, node, l, r, i, value):
    if l == r:
        self.tree[node] = value
        return
    mid = (l + r) // 2
    if i <= mid:
        self._update(2 * node, l, mid, i, value)
    else:
        self._update(2 * node + 1, mid + 1, r, i, value)
    self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

The program above adds the print lines to this method, so you can see the path. The real code does not need them.

Why the update chooses one child

Look at the line that chooses the child: if i <= mid. The index i belongs to exactly one half of every segment it lies in. If i is at most mid, it is in the left half, and the right half is untouched. If i is greater than mid, it is in the right half. Only one child is ever recursed into, which is why the update costs one path and not two.

It is easy to write the test wrongly. A common mistake is to compare i with l or r instead of mid. Comparing with l would send the update right whenever i is past the left end, which is almost always, so the change lands in the wrong half. Always compare with mid, because that is the boundary the tree was built with.

Turning the sum tree into a minimum tree

Now the second operation. Suppose you need the smallest value in a range instead of the sum. This is a range minimum query. Imagine a weather station that records a temperature for each hour, and you want the coldest hour in a window.

The tree is the same shape. Only two things change. First, a node stores the minimum of its segment instead of the sum. A parent is the smaller of its two children, so it uses min instead of +. Second, the answer for a range with no overlap must be a value that never wins a minimum. Zero would be wrong, because 0 is smaller than any positive value and would win those comparisons. The neutral value for minimum is the largest possible number. In Python that is float("inf"), which is larger than any int.

The complete program below builds a minimum tree, answers two queries, updates one value, and answers two more queries. Press Run, since its data is fixed.

The output is:

2
3
3
5

Check each answer. Indexes 1 to 3 hold 2, 8 and 6, and the smallest is 2. Indexes 2 to 4 hold 8, 6 and 3, and the smallest is 3. After update(1, 9) the list is [5, 9, 8, 6, 3]. The smallest of all five values is 3. Indexes 0 to 2 hold 5, 9 and 8, so the smallest is 5.

The structure of the code is identical to the sum version. The build, the query and the update each have the same shape. The only differences are min in place of +, and float("inf") in place of 0 for the no-overlap case. That is a useful habit to notice. Most tree operations share one shape, and the operation itself is a small detail.

Driving the tree from a list of commands

Programs get more useful when the data arrives as commands. The next program stores the commands in a list. A command ("Q", l, r) asks for the minimum from l to r, and it prints one line. A command ("U", i, v) sets item i to v, and it prints nothing. Replace the list with lines read by input() when you run the program on your own computer.

The output is:

2
3
3
5

These are the same four answers as the fixed example, and you did not change any code to get them. That is the point of a command loop. The same program answers any sequence of commands.

Read the loop closely. The tuple (op, x, y) unpacks three values at once, which is a common Python pattern. The test op == "Q" compares text, and in Python == compares the content of two strings. That is the right test here. Python also has is, which compares object identity, but for strings you almost always want ==.

If you read the commands from the keyboard with input(), every line arrives as text. Split it with line.split(), then convert the numbers with int().

The rule for a combine operation

For a tree to answer a range query, the operation must follow two rules. The first rule is that the operation is associative. That means grouping does not matter, so (a + b) + c equals a + (b + c). This is why the tree can split a range at any point and still get the right answer. Sum, minimum, maximum, gcd and bitwise AND all have this property.

The second rule is that the operation has a neutral value. A neutral value is a number that changes nothing when combined. For sum it is 0, because x + 0 is x. For minimum it is the largest value, because min(x, big) is x. The query needs this value for the no-overlap case, so the search can combine it without changing the answer.

Some operations fail the first rule when stored in a single number. Average is the classic example. The average of the averages of two groups is not the average of the combined group, unless the groups have the same size. The fix is to store a sum and a count, combine both, and divide at the end. The operation then becomes associative, and the tree works. The lesson is that the stored value does not have to be the final answer. It only has to combine correctly.

Here is a table of common operations and their neutral values. Use it when you design a new tree.

One generic tree for many operations

Writing a separate tree class for each operation repeats the same code. Python functions are values, so you can pass the combine rule as an argument. The standard library already has functions for the common cases. The operator module has operator.add, and min, max and math.gcd are functions too. A lambda is a short unnamed function, written as lambda x, y: x * y.

The next program builds four trees on the same list, one each for sum, minimum, maximum and gcd. Each tree receives its operation and its neutral value when it is created. The build and query code is written once.

The output is:

sum 0..4 = 112
min 1..3 = 18
max 0..2 = 30
gcd 0..2 = 6
gcd 3..4 = 1

Check the gcd lines by hand. The greatest common divisor of 12, 18 and 30 is 6, because 6 divides all three and nothing larger does. The gcd of 45 and 7 is 1, since they share no factor. The sum of all five values is 12 + 18 + 30 + 45 + 7 = 112.

The gcd tree relies on the neutral value 0. The rule is gcd(0, x) = x, so combining with an empty part changes nothing. That is why 0 works for gcd even though it would fail for minimum. You can check it directly with math.gcd(0, 7), which returns 7.

The argument min is the built-in function itself, passed without parentheses. Writing min(...) would call it right away, which is not what the constructor needs. The class does not know which operation it has. That is the whole trick of a generic structure.

One detail is worth noting. Python integers never overflow, so the sum of large values is always exact. That is different from int in some other languages, where a large sum can wrap around. The trade-off is that very large integers take more memory and time.

Finding the first item that is small enough

Now a pattern that appears often in interviews. Suppose you need the first index, starting from a given position, whose value is at most some limit x. For example, a warehouse wants the first shelf at or after position l that has at most 4 items left. A plain loop would walk the shelves one by one. A minimum tree can skip whole blocks at once.

The idea is this. If a node's minimum is greater than x, then no item in that segment is small enough, so the whole segment can be skipped at once. If the node's minimum is at most x, then at least one item in the segment qualifies, so the answer is inside that segment. The search goes left first, because the left child covers earlier indexes, and the first index found is the answer.

The method has to handle one more detail. A segment may start before l. Items before l must not count. So the search returns -1 for any segment that ends before l. When it reaches a leaf that is inside the allowed range and small enough, the leaf's index is returned.

The next program builds a minimum tree over six values and answers four searches. Each search has a start index and a limit.

The output is:

1
3
4
-1

Check each line. The list is [7, 4, 9, 2, 8, 5]. From index 0, the first value at most 4 is index 1, which holds 4. The second query starts at index 1 with limit 3. Index 1 holds 4, which is too big. Index 2 holds 9, also too big. Index 3 holds 2, which is at most 3, so the answer is 3. From index 4, the first value at most 10 is index 4 itself, which holds 8. From index 4 with limit 1, indexes 4 and 5 hold 8 and 5, and neither is at most 1, so the answer is -1.

The search takes the tree's shape into account. When tree[node] > x, the whole segment is skipped in one comparison. A segment whose minimum is at most x always contains an answer, unless the answer lies before l. When the search enters such a segment, it either finds the answer on the left or, if the left part does not qualify, goes right. The total work stays near one path down the tree, so the search costs O(log n).

What happens inside Python

The point update and the find-first search both use the call stack, as the query did in the second lesson. The update goes down one path and back up. Each frame stays on the stack while its child works. When the leaf changes, the stack unwinds, and each parent recomputes itself from the child that just finished. That unwinding is where the parents get their new values.

The generic tree stores its operation as an attribute, self.op. A function object is called with the same syntax as any other function, so the cost of self.op(a, b) is only a little more than writing a + b in the code. For learning and for most programs the cost is too small to matter. In a very hot loop, a specialised version with the operator written inline may be faster. Measure before you change the code.

The find-first search can call itself on both children. In the worst case it looks at both branches of a node. The argument for O(log n) is that every branch that fails stops at once, because its minimum is too big or it lies before l. Only one branch can succeed in a full descent, and that descent has one call per level.

Common mistakes

Forgetting to recompute parents after an update. The leaf changes, but its parents keep the old values. Every query that uses a parent returns a wrong answer. The fix is the recomputation line after the recursive call, and the trace program above shows it clearly.

Using 0 as the neutral value for minimum. Zero is smaller than any positive value, so over positive data it wins every minimum and the answer is 0. The neutral value must be larger than every value the tree can hold, so use float("inf").

Choosing the child by comparing with l or r. The child choice must compare the index with mid. Comparing with the ends sends updates to the wrong side, which corrupts the tree quietly.

Rebuilding the whole tree after each update. A rebuild costs O(n), which defeats the purpose. A point update must touch one path only.

Typing a letter where a number is expected. When the program reads a command such as Q x 3 from the keyboard, the code int("x") fails. Python reports this:

ValueError: invalid literal for int() with base 10: 'x'

The name ValueError says the value had the right type, a string, but the wrong content for a number. The text after the colon shows the piece that could not be converted. Check the input for a letter where a number should be. In a Q command the two numbers are the left and right ends. In a U command they are the index and the new value.

Mixing up the start position and the limit. In find_first, the first argument is a position where the search starts, and the second is a value limit. Swapping them does not cause an error, but it finds the wrong index. Name your variables clearly, as the code above does, so you can see which is which.

Debugging walkthrough: a minimum that is too small

Suppose a minimum query returns a number that is smaller than every value in the range. The usual cause is a neutral value of 0 for the no-overlap case. Check the no-overlap line first. If it says return 0, that is the bug. Change it to float("inf"), then run the trace again to confirm that partly covered nodes now return the right minimum.

If the query returns a number that is too big, the cause is usually a missing full-overlap check, or an update that did not reach the parents. Run the update trace and look at the printed path. Every node on the path should change, and the root should match the new total. If a parent does not change, the recomputation line is missing or uses the wrong children.

Variations to know

Minimum with the position. Interviewers often ask for the minimum and the index where it occurs. Store a pair (value, index) in the tree, and use a combine function that picks the pair with the smaller value. Python compares tuples element by element, so min((5, 0), (2, 3)) gives (2, 3). The structure is the same, but the stored thing is a pair.

Range add with minimum. Adding a value to every item in a range, and asking for the minimum, needs lazy propagation, which the next lesson covers.

Maximum with a window. A sliding window maximum is often solved with a deque, but a segment tree also handles arbitrary windows. Use it when the windows do not slide in order.

Counting values below a limit. Store a sorted list in each node and use bisect to binary search it. That is a different structure called a merge sort tree, and it is a stretch topic. Mention it if asked, but do not build it in an interview without warning.

Interview questions this lesson prepares you for

"How do you update one element?" Walk down the one path to the leaf, change the leaf, and recompute each parent on the way back. The cost is O(log n). Mention that you compare with mid to choose the side.

"What is the neutral value for minimum?" A value larger than every item, which in Python is float("inf"). Explain that the neutral value must never win the comparison, and that 0 would break the answer.

"What properties must an operation have to work in a segment tree?" It must be associative, so the tree can split the range anywhere, and it must have a neutral value for empty overlaps. Give sum, minimum and gcd as examples, and average as the case that needs a sum and count.

"How do you find the first element at least some value after position l?" Use a minimum tree with the find-first descent. Explain the skip rule: a segment whose minimum is too big is skipped in one comparison, and the search goes left first.

Following one update through the minimum tree

Here is the same update as the sum example, but on the minimum tree. Start with the list [5, 2, 8, 6, 3]. Its tree stores these minimums: the root is 2, the node [0..2] is 2, the node [0..1] is 2, and the leaf for index 1 is 2. The node [3..4] is 3, and the leaves for indexes 3 and 4 hold 6 and 3.

Now call update(1, 9), which changes index 1 from 2 to 9. The leaf for index 1 becomes 9 first. The parent [0..1] is recomputed as the smaller of its children, which are 5 (index 0) and 9 (index 1). So it becomes 5, up from 2. The node [0..2] is recomputed next. Its children are [0..1], now 5, and the leaf for index 2, which is 8. The smaller is 5, so [0..2] also becomes 5. At the root, the children are [0..2], now 5, and [3..5], which is 3. The root becomes 3.

Only four nodes changed: the leaf and its three ancestors. The node [3..4] did not change, because index 1 is not inside it, so it kept its old minimum of 3. Notice how the root moved from 2 to 3. The old minimum 2 disappeared when index 1 changed, so the root had to find the next smallest value. Only the recomputation on the way back up can do that. A tree that skipped the recomputation would still say 2 at the root, and every query that reached the root would be wrong.

This example also shows why a minimum is harder to keep right than a sum. A sum changes by the difference, which you can compute without looking at the other children. A minimum can rise when its smallest item is removed, and the only way to learn the new minimum is to look at the other items again. That is why the recomputation uses both children every time.

Why zero breaks the minimum tree: a concrete case

The neutral value is easy to get wrong, so here is one concrete case that shows the damage. Use the same list [5, 2, 8, 6, 3] and ask for min(0, 0), which is just the first item, 5.

The root covers [0..4] and is partly covered. Its left child [0..2] is partly covered. Its child [0..1] is partly covered. Inside that node, the leaf for index 0 is fully covered and returns 5. The leaf for index 1 is outside the query, so it has no overlap and returns the neutral value. Then the min at the parent combines the two answers, 5 and the neutral value.

If the neutral value is 0, the parent computes min(5, 0), which is 0. The answer is wrong, because the first item is 5 and nothing smaller is in the range. The zero leaked in from a position that was never part of the query. If the neutral value is float("inf"), the parent computes min(5, inf), which is 5. The outside position disappears from the answer, which is what it should do.

Test this case every time you write a minimum tree. It is one line of code to check, and it catches the most common version of this bug. With 0 as the neutral value the tree fails on positive data and looks right on negative data, so test both kinds.

Testing the minimum tree against a loop

The check from the second lesson works for minimums too. Build a minimum tree for every size from 1 to a dozen or so. For each size, test every range against a loop that takes the minimum by hand. Compare the answers. The loop is slow but obviously correct, so it is the right reference.

Add a few updates to the test as well. After each update, test a few ranges against the loop. Updates are where the recomputation bugs hide, because the mistake only shows up after the tree has changed once. A test that only builds and queries does not reach that part of the code.

Use random data with both positive and negative values. Negative values alone hide the neutral value bug, because min(x, 0) is x when x is negative, so the positive values are the ones that expose it, as the concrete case above showed.

Find-first in an interview

The find-first search is a common interview question with a longer version. The usual question is "given a list and a start index, find the first index at or after it whose value is at least k." The answer is the same pattern, with the comparison reversed. Use a maximum tree instead of a minimum tree, and skip any segment whose maximum is less than k.

Interviewers often follow up with a question about sums. "Find the first index where the running total from the start reaches k." If the values are not negative, the running total only grows, so a sum tree can search for it. At each node, compare k with the sum of the left child, and descend left if the left sum already reaches k, or subtract the left sum and descend right otherwise. That works only when the values are not negative, and a strong answer says so.

When you answer, name the rule you rely on. The find-first search works because a segment that cannot contain the answer can be skipped in one comparison. The sum version works because the running total is monotone, so a single comparison picks the correct half. Naming the rule shows that you are using a property of the data, not guessing.

Why one generic class is a design choice

The generic tree is good engineering because it puts the operation in one place. A bug in the build or the query is fixed once, and every operation benefits. It also makes the code easier to test, because the same test works for sum, minimum and gcd by changing one argument.

There is a cost. The operation is called through a stored function, so each combine is a function call. For most programs the cost is invisible. For a tight loop that runs billions of times, a specialised class may be faster.

Make the choice on purpose. Prefer the generic class while you are learning and while the operation may change. Switch to a specialised class if a profile shows the call overhead matters. In an interview, you can mention both and say which one you would start with.

Practice

1. What is the maximum tree's neutral value, and what happens to a maximum query if you use 0 instead?

Show the answer

The neutral value is float("-inf"). If you use 0 and every real value is negative, the no-overlap case returns 0. That is bigger than all the real values, so 0 wins and the answer is wrong. With only positive values, 0 would happen to give the right answer, but that is luck. The rule is that the neutral value must never win the comparison for any data.

2. After update(4, 1) on the example list [5, 2, 8, 6, 3], what does min(0, 4) return? Give the new list first.

Show the answer

The new list is [5, 2, 8, 6, 1]. The update changed index 4 from 3 to 1. The smallest value is now 1, so the answer is 1.

3. Explain why average is not a valid combine rule when stored directly in each node. Give a counterexample with two groups of different size.

Show the answer

Take the group [2, 4] with average 3, and the group [10] with average 10. The average of those two averages is (3 + 10) / 2 = 6.5. The true average of [2, 4, 10] is 16 / 3, which is about 5.33. The parent gives the wrong answer because it gave each group equal weight. A sum and a count fix this, because the combined sum divided by the combined count is correct.

4. Write the Python line that updates the parent after its children change, for a minimum tree.

Show the answer

self.tree[node] = min(self.tree[2 * node], self.tree[2 * node + 1])

This line runs after the recursive call returns, so both children are already up to date.

5. The update method compares i with mid. Describe what would go wrong if it compared i with l instead.

Show the answer

Comparing with l asks whether i is at most the left end, which is almost never true. Almost every update would then go right, so the changed item would land in the right child even when its index lies in the left half. The tree would then store the change in the wrong segment, and queries would be wrong. The boundary that splits the tree is mid, so the comparison must use it.

6. The find-first search returns -1 for a node whose minimum is greater than x. Explain why it is safe to skip the whole segment without looking inside.

Show the answer

The minimum of a segment is the smallest value in it. If the smallest value is greater than x, every value in the segment is greater than x, so none of them qualifies. Looking inside would only confirm what the stored minimum already says. Skipping is therefore safe and saves work.

7. In the find-first search, why must the check nr < l come before the left and right recursion?

Show the answer

The check nr < l says the whole segment lies before the start position, so its items are not allowed to answer the query. If the check came after the recursion, the search could return an index before l. Putting the check first also stops the search from going into a segment that cannot help, which keeps the work small.

8. Write the lambda that makes a tree compute the product of its items. What neutral value should it use, and why?

Show the answer

SegTree(a, lambda x, y: x * y, 1)

The neutral value is 1, because x * 1 equals x. Using 0 would make every product 0, because x * 0 is 0 for any x. The product is also an associative operation, so the tree combines it correctly.

9. The text Q x 3 is read from the keyboard, and the program calls int on each piece. Which call fails, and why does the program stop there?

Show the answer

The call int("x") fails. The program splits the line into Q, x and 3, then converts the pieces that should be numbers. The text x cannot be read as a whole number, so Python raises ValueError. Nothing catches it, so Python prints the error and the program stops.

What you now know

• A point update changes one leaf and recomputes its ancestors on the way back up. It touches one path, so it costs O(log n).
• The update compares the index with mid to choose the side. Comparing with the ends is a common and silent bug.
• For minimum queries the tree stores the minimum, combines with min, and uses float("inf") as the neutral value for no overlap.
• A combine operation must be associative and have a neutral value. Average fails unless you store a sum and a count.
• A generic tree takes the operation and the neutral value as arguments, so one class serves sum, minimum, maximum and gcd.
• The find-first search skips any segment whose minimum is too big, and it goes left first to return the earliest index.

The next lesson adds lazy propagation for updates that change a whole range at once, and introduces the Fenwick tree as a compact alternative for sums.