Debugging lab: segment tree bugs in Python

Why this matters

Some bugs in a segment tree crash the program with a clear message. Many do not. A broken tree often prints a number that looks plausible and is wrong. A query that covers a whole list can still be right while a query on part of it is wrong, so a quick test can pass and the bug stays hidden.

This lab gives you three broken programs. For each one, you run the program, read the output, find the cause and fix it. The programs are short, so you can read all of each one. The build, point update and lazy tag ideas used here come from the earlier lessons in this module, the point updates and lazy propagation lessons in particular.

Each section below shows the broken code, the real output and the fix. Run each program yourself in a folder of your own. Your output should match the output shown. The folder path in a traceback and the marker lines under the code depend on your machine and Python version.

A method for finding segment tree bugs

Use the same steps for every bug in this lab.

1. Make the input as small as you can. A tree with 5 or 6 values is easy to trace by hand.
2. Read the last line of any error message. It names the exception and the problem.
3. Read the traceback from the bottom up. The bottom lines show the place that failed, and the lines above them are the calls that led there. The line numbers point to the code.
4. For a wrong answer, pick one query and compute the right answer by hand or with a brute-force loop. Brute force means trying every case, which is slow but easy to trust.
5. Change one thing at a time, then run again.

A traceback is the list of function calls that were active when the error happened. Python prints it when an error is not caught.

Bug 1: the list is too small

A segment tree is often stored in a plain list. Node 1 is the root, and the children of node i are 2 * i and 2 * i + 1. This numbering gives every node a fixed index, so a tree of n values needs a list long enough for the largest index it uses.

The largest index is not 2 * n. A node's index doubles at each level, and the leaves do not all sit at the same depth, so the largest index can go past 2 * n. Many programs write 2 * n out of habit, because a binary tree with n leaves has about 2 * n nodes. That count is for a tree with compact numbering, not for this one.

The program below builds a sum tree for six values but makes the list only 2 * n slots long.

tree = []
 
 
def build(a, node, l, r):
    if l == r:
        tree[node] = a[l]
        return
    mid = (l + r) // 2
    build(a, 2 * node, l, mid)
    build(a, 2 * node + 1, mid + 1, r)
    tree[node] = tree[2 * node] + tree[2 * node + 1]
 
 
a = [4, 1, 7, 2, 9, 3]
n = len(a)
tree = [0] * (2 * n)
build(a, 1, 0, n - 1)
print("total =", tree[1])

The output is:

Traceback (most recent call last):
  File "bug1.py", line 17, in <module>
    build(a, 1, 0, n - 1)
    ~~~~~^^^^^^^^^^^^^^^^
  File "bug1.py", line 10, in build
    build(a, 2 * node + 1, mid + 1, r)
    ~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "bug1.py", line 9, in build
    build(a, 2 * node, l, mid)
    ~~~~~^^^^^^^^^^^^^^^^^^^^^
  File "bug1.py", line 9, in build
    build(a, 2 * node, l, mid)
    ~~~~~^^^^^^^^^^^^^^^^^^^^^
  File "bug1.py", line 6, in build
    tree[node] = a[l]
    ~~~~^^^^^^
IndexError: list assignment index out of range

Read the last line first. "list assignment index out of range" says that the code wrote to a slot that is not in the list. The bottom frame is line 6, tree[node] = a[l], which is the leaf write. The frames above it show the path of calls. The first call is on line 17, which starts the build at the root. Line 10 is the right child call, and line 9 is the left child call, twice. Starting at the root, the path goes right to node 3, then left to node 6, then left to node 12. Node 12 is the leaf for index 3, and it is the first slot past the end of a list of 12 slots.

The build also needs slot 13 later, which is past the end too. The traceback stops at the first failing write, which is node 12.

The fix is to make the list 4 * n slots long:

tree = [0] * (4 * n)

Running the fixed program prints:

total = 26

The total of 4, 1, 7, 2, 9, 3 is 26, so the output is right.

The number 4 * n is the usual size for this numbering. The leaves do not all sit at the same depth, so some of the 4 * n slots are not used. That is a small cost for a safe list. To check the size for a given n, build the tree once with a recursive walk that records the largest index it visits. The largest index for 10 values is 25, which is above 2 * 10 - 1, and the list of 4 * 10 slots holds it.

Python integers do not overflow, so the midpoint (l + r) // 2 is safe for any length. Languages with fixed-size integers need a different midpoint form for very large ranges. That concern does not apply here.

Bug 2: the identity value is wrong

A query that covers only part of a node has to combine the answer from its children, and some children do not overlap the query at all. Those children return an identity value. An identity value does nothing when combined with another value, so combining it leaves the answer unchanged.

The identity depends on the operation:

• For sum, the identity is 0, because x + 0 is x.
• For product, the identity is 1, because x * 1 is x.
• For minimum, the identity is a very large number, such as float("inf"), because min(x, inf) is x.
• For maximum, the identity is a very small number, such as float("-inf").

Zero is a common default, so it is easy to use by accident. Zero works for sums, but it breaks a minimum query, because min(0, x) is always 0 when x is positive.

The program below builds a minimum tree for five values. It sets the identity to 0 by mistake.

NONE = 0
tree = []
 
 
def build(a, node, l, r):
    if l == r:
        tree[node] = a[l]
        return
    mid = (l + r) // 2
    build(a, 2 * node, l, mid)
    build(a, 2 * node + 1, mid + 1, r)
    tree[node] = min(tree[2 * node], tree[2 * node + 1])
 
 
def query(node, l, r, ql, qr):
    if qr < l or r < ql:
        return NONE
    if ql <= l and r <= qr:
        return tree[node]
    mid = (l + r) // 2
    return min(query(2 * node, l, mid, ql, qr), query(2 * node + 1, mid + 1, r, ql, qr))
 
 
a = [5, 7, 9, 3, 8]
n = len(a)
tree = [0] * (4 * n)
build(a, 1, 0, n - 1)
print("min of [1,2] =", query(1, 0, n - 1, 1, 2), "(expected 7)")
print("min of [3,4] =", query(1, 0, n - 1, 3, 4), "(expected 3)")

The output is:

min of [1,2] = 0 (expected 7)
min of [3,4] = 0 (expected 3)

Both answers are wrong, and neither gives an error. Here is what happens in the first query. The range [1,2] covers the values 7 and 9. The node for [0,1] overlaps the query only at index 1. Its child for [0,0] does not overlap, so it returns NONE, which is 0. Its other child for [1,1] returns 7. The node takes min(0, 7), which is 0. The 0 from the identity was merged into the answer, and it is smaller than every real value.

The fix is to use the right identity for minimum:

NONE = float("inf")

The output after this change is:

min of [1,2] = 7 (expected 7)
min of [3,4] = 3 (expected 3)

A whole-range query does not show this bug. It returns the root directly, so the identity is never merged. This is why a test that only asks for the whole list can pass. Always include queries that cut through a node, such as [1,2] in this program.

The same mistake with a sum tree gives no wrong answer, because 0 is the right identity for sums. A correct test on the operation you chose is what catches it.

Bug 3: lazy tags pushed in the wrong order

A lazy tag is a pending update stored at a node. The update has not yet been written into the child nodes below it. A later query or update pushes (copies) the tag down one level when it needs the children. This keeps each update cheap. The lazy idea is taught in the lazy propagation lesson of this module, so this section only covers the order problem.

The program in this section supports two range operations. set sets every value in a range to one number. add adds one number to every value in a range. Order matters. If the value is 1, setting it to 10 and then adding 3 gives 13. Adding 3 and then setting it to 10 gives 10.

So a node that has both a pending set and a pending add has to remember them in the order they happened. The rule is this. A pending set makes the value set_value. A pending add after that changes the value to set_value + add_tag. When a node pushes its tags to its children, it must apply the set first, then the add. Applying the add first and the set second throws the add away, because the set overwrites the value.

The program keeps its four lists in one dictionary, T, so that each helper can be passed the same data. The program below pushes the add tag first. This is the bug.

def make(n):
    return {"sum": [0] * (4 * n), "add": [0] * (4 * n), "set": [0] * (4 * n), "has": [False] * (4 * n)}
 
 
def apply_set(T, node, length, v):
    T["sum"][node] = v * length
    T["set"][node] = v
    T["has"][node] = True
    T["add"][node] = 0
 
 
def apply_add(T, node, length, d):
    T["sum"][node] += d * length
    T["add"][node] += d
 
 
# Bug: the add tag is pushed to the children before the set tag.
def push(T, node, l, r):
    mid = (l + r) // 2
    left_len = mid - l + 1
    right_len = r - mid
    if T["add"][node] != 0:
        apply_add(T, 2 * node, left_len, T["add"][node])
        apply_add(T, 2 * node + 1, right_len, T["add"][node])
        T["add"][node] = 0
    if T["has"][node]:
        apply_set(T, 2 * node, left_len, T["set"][node])
        apply_set(T, 2 * node + 1, right_len, T["set"][node])
        T["has"][node] = False
 
 
def build(T, a, node, l, r):
    if l == r:
        T["sum"][node] = a[l]
        return
    mid = (l + r) // 2
    build(T, a, 2 * node, l, mid)
    build(T, a, 2 * node + 1, mid + 1, r)
    T["sum"][node] = T["sum"][2 * node] + T["sum"][2 * node + 1]
 
 
def update(T, node, l, r, ql, qr, kind, v):
    if qr < l or r < ql:
        return
    if ql <= l and r <= qr:
        if kind == "set":
            apply_set(T, node, r - l + 1, v)
        else:
            apply_add(T, node, r - l + 1, v)
        return
    push(T, node, l, r)
    mid = (l + r) // 2
    update(T, 2 * node, l, mid, ql, qr, kind, v)
    update(T, 2 * node + 1, mid + 1, r, ql, qr, kind, v)
    T["sum"][node] = T["sum"][2 * node] + T["sum"][2 * node + 1]
 
 
def query(T, node, l, r, ql, qr):
    if qr < l or r < ql:
        return 0
    if ql <= l and r <= qr:
        return T["sum"][node]
    push(T, node, l, r)
    mid = (l + r) // 2
    return query(T, 2 * node, l, mid, ql, qr) + query(T, 2 * node + 1, mid + 1, r, ql, qr)
 
 
a = [1, 1, 1, 1]
T = make(len(a))
build(T, a, 1, 0, 3)
update(T, 1, 0, 3, 0, 3, "set", 10)   # every value becomes 10
update(T, 1, 0, 3, 0, 3, "add", 3)    # every value becomes 13
print("sum of all =", query(T, 1, 0, 3, 0, 3), "(expected 52)")
print("value at 0 =", query(T, 1, 0, 3, 0, 0), "(expected 13)")
print("sum of [2,3] =", query(T, 1, 0, 3, 2, 3), "(expected 26)")

The output is:

sum of all = 52 (expected 52)
value at 0 = 10 (expected 13)
sum of [2,3] = 20 (expected 26)

The first line is correct, and that is why the bug is easy to miss. The root keeps its own sum up to date every time an operation runs, so a query that asks for the whole list reads the root and never pushes. The wrong values appear only when a query goes down into the children.

Here is what happens. After the two operations, the root holds a pending set of 10 and a pending add of 3. Its correct meaning is "set to 10, then add 3", which gives 13 for each value. When a query goes down, push runs. It gives the children the add of 3 first. The left child covers two positions, so its sum goes from 2 to 8, and it keeps 3 as its own pending add. Then push gives the children the set of 10. That sets each child's values to 10 and clears the pending add. The add of 3 is lost. The children now hold 10, not 13.

The fix is to push the set first and the add second. Only the push function changes. The rest of the program stays the same.

# Fix: the set tag is pushed first, then the add tag, because the add came after the set.
def push(T, node, l, r):
    mid = (l + r) // 2
    left_len = mid - l + 1
    right_len = r - mid
    if T["has"][node]:
        apply_set(T, 2 * node, left_len, T["set"][node])
        apply_set(T, 2 * node + 1, right_len, T["set"][node])
        T["has"][node] = False
    if T["add"][node] != 0:
        apply_add(T, 2 * node, left_len, T["add"][node])
        apply_add(T, 2 * node + 1, right_len, T["add"][node])
        T["add"][node] = 0

The output after the fix is:

sum of all = 52 (expected 52)
value at 0 = 13 (expected 13)
sum of [2,3] = 26 (expected 26)

The fix depends on one detail in apply_set. It sets the add tag to 0. A new set wipes out any older pending add, because the set writes every value from scratch. If that line is removed, an add from before the set would come back after the set.

A related mistake is reading a child before the parent has been pushed. A query that looks at a child without first calling push on the parent gets a stale value. Every function that goes down into the children must push first.

Common mistakes

Trusting a whole-list test. The root holds the full answer, so a query over the whole list reads the root and skips the children. Bugs 2 and 3 both appear only in partial queries. Test a range that starts in the middle, and test a single position.

Testing only small lists. A tree with 2 to 5 values can work with 2 * n slots, because its largest index sometimes stays below 2 * n. The bug appears at 6 values. Test with several sizes, including sizes that are not powers of 2.

Mixing up the identity and the first value. The identity is what a non-overlapping node returns. It is not the first value in the list, and it is not the value of an empty range. For minimum it must be bigger than any real value, and for maximum it must be smaller.

Confusing a traceback with the cause. The bottom line of a traceback is the error, but the cause can be higher up. In bug 1 the error is on line 6, and the cause is the list size set on line 16. Read the lines of your own code that set up the data, not only the line that failed.

Practice

1. Use the numbering from bug 1. For a list of 10 values, find the largest node index that the build can use, and say whether [0] * (2 * 10) is big enough.

Show the answer

The largest index is 25. Since 2 * 10 is 20, the slots run from 0 to 19, and index 25 is past the end. The list [0] * (4 * 10) has slots 0 to 39, which is enough.

2. The list 8, 2, 6 is loaded into a minimum tree with identity 0. What does query(1, 0, 2, 0, 0) return, and what should it return?

Show the answer

It returns 0. It should return 8. The root covers [0,2] and the query covers only index 0. The node for [0,1] takes its left child, which is 8, and its right child for index 1 does not overlap the query, so it returns the identity 0. The node takes min(8, 0), which is 0. The right child of the root, for index 2, also returns 0. Changing the identity to float("inf") gives 8.

3. A sum tree of two values, both 1, gets a set of 5 on both values and then an add of 2 on both values. A query for index 0 is asked next. Predict the buggy answer and the fixed answer, then check by running the program.

Show the answer

The buggy push gives 5, and the fixed push gives 7. The correct value is 5 plus 2, which is 7. The buggy push applies the add to the leaf first and then the set overwrites it, so the leaf holds 5.

4. In the buggy program of bug 3, the output says sum of all = 52, which is correct, while value at 0 is wrong. Explain why both can be true at the same time.

Show the answer

The root's sum is updated by each operation, so it is right even though the children still hold stale values. The whole-list query reads the root and never goes down, so it sees the right total. The query for index 0 goes down through the root, and the wrong push order gives the leaf the wrong value.

Summary

• Size the list for the node numbering you use. For the numbering in this module, 4 * n is the usual safe size, and 2 * n fails for some n, such as 6.
• The identity must not change the answer when combined. Use 0 for sums, 1 for products, a very large value for minimum and a very small value for maximum.
• Lazy tags must be pushed in the order the updates happened. For a set followed by an add, push the set first.
• A whole-list query can hide bugs, so test partial ranges and single positions.
• Check every operation at several sizes with a brute-force answer before you trust the tree.