Debugging lab: segment tree bugs

Why this matters

A segment tree bug often does not look like a bug. The program compiles, runs and prints numbers. Some of the numbers are wrong, and only some queries are wrong. A test on the whole array may pass while a test on a middle range fails. The fastest way to find the cause is to make a small input, work out the right answer on paper, and compare it with the program's output one line at a time.

This lab gives three buggy programs. Each has one kind of mistake that shows up often when people write segment trees:

• a tree that is too small, where the vector holding the nodes has fewer slots than the tree needs
• a neutral value set wrong, where the answer for an empty part of the range is a number that changes the result
• lazy tags pushed in the wrong order, where a pending update is applied after the children were already changed

A lazy tag is a note stored on a node that says "the children of this node are out of date, and must be set to this value". The lesson on lazy tags explains the idea in full. This lab assumes you know it.

Each program is one file, and each file has a main function that runs it. Compile each one with:

g++ -std=c++20 -Wall -o bug1 bug1.cpp
./bug1

A checklist for segment tree bugs

Use these four checks in order. Most bugs are caught by one of them.

1. Size. Count the slots the vector needs for the largest node number. Do not guess. A recursive tree whose root is node 1 can use node numbers larger than 2 * n.
2. Neutral values. For each place the code returns something for a range with no positions, ask what value keeps the answer unchanged when it is combined with a real answer. Zero is neutral for a sum. It is not neutral for a minimum.
3. Lazy order. For each node that has a pending tag, ask whether the tag is pushed to the children before the children are touched, and whether the tag is cleared after it is pushed.
4. Small input. Run the program on an array of 3 to 6 values. Work out the answer for two or three queries by hand. Print the answers and compare them.

When you debug, use .at() instead of [] for vector access. .at() checks the index and throws an exception when the index is out of range. [] does not check, so a bad index can read or write memory that the vector does not own. The check costs a little speed, so remove it after the bug is fixed if speed matters.

Bug 1: a tree that is too small

The first program builds a sum segment tree. It stores the node values in a std::vector, and it sizes that vector at 2 * n. Read it and find the mistake before you run it.

#include <iostream>
#include <vector>
 
class SumTree {
public:
    // BUG: the tree needs more room than 2 * n slots.
    explicit SumTree(const std::vector<long long>& a)
        : n_(static_cast<int>(a.size())), t_(2 * a.size()) {
        build(1, 0, n_ - 1, a);
    }
 
    long long query(int l, int r) const { return query(1, 0, n_ - 1, l, r); }
 
private:
    void build(int node, int lo, int hi, const std::vector<long long>& a) {
        if (lo == hi) {
            t_.at(node) = a[lo];
            return;
        }
        int mid = lo + (hi - lo) / 2;
        build(2 * node, lo, mid, a);
        build(2 * node + 1, mid + 1, hi, a);
        t_.at(node) = t_.at(2 * node) + t_.at(2 * node + 1);
    }
 
    long long query(int node, int lo, int hi, int l, int r) const {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return t_.at(node);
        int mid = lo + (hi - lo) / 2;
        return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
    }
 
    int n_;
    std::vector<long long> t_;
};
 
int main() {
    SumTree st({1, 2, 3, 4, 5, 6});
    std::cout << "sum of all: " << st.query(0, 5) << '\n';
    std::cout << "sum of [2,4]: " << st.query(2, 4) << '\n';
}

Run it. The output is:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 12) >= this->size() (which is 12)

The program stops with exit code 134. The message says the program tried to use index 12 in a vector that has 12 slots. Slots are numbered 0 to 11, so index 12 is one past the end.

Trace the numbers to see why. The tree for 6 values has the root at node 1, and it covers positions 0 to 5. Its children are nodes 2 and 3. The build function goes left first, so it reaches the leaves of the left half before the right half. The right half of the array is positions 3 to 5. That half splits again into positions 3 to 4 at node 6, and position 5 at node 7. Position 3 is node 12, which is the first node number the build reaches that is past the end of the vector. The largest node number used is 13, so a vector of 14 or more slots is needed.

The rule for the largest node number is this. The depth of a tree over n leaves is at most the logarithm of n, rounded up. The root has depth 0. Every node at depth k has a number from 2^k up to 2^(k+1) - 1. So the largest node number is less than 2^(d+1), where d is the largest depth. Since 2^d is less than 2n, the number 2^(d+1) is less than 4n. So 4 * n slots are always enough.

Fix the constructor:

    explicit SumTree(const std::vector<long long>& a)
        : n_(static_cast<int>(a.size())), t_(4 * a.size()) {

The program then prints:

sum of all: 21
sum of [2,4]: 12

The sum of 3, 4, 5 is 12, which matches. Sizing the vector at 2 * n is a common mistake because it works for many small sizes. For this code, the first size that fails is n = 6. A size of 3 still works, because the largest node number for 3 values is 5, and 2 * 3 = 6 slots are enough. The safe rule is 4 * n.

Bug 2: a neutral value set wrong

The second program is a minimum segment tree. It answers "what is the smallest value between positions l and r?" Its query returns 0 when the node lies outside the range. The author chose 0 because it looked like "nothing here".

#include <algorithm>
#include <iostream>
#include <vector>
 
class MinTree {
public:
    explicit MinTree(const std::vector<long long>& a) : n_(static_cast<int>(a.size())), t_(4 * a.size()) {
        build(1, 0, n_ - 1, a);
    }
 
    long long query(int l, int r) const { return query(1, 0, n_ - 1, l, r); }
 
private:
    void build(int node, int lo, int hi, const std::vector<long long>& a) {
        if (lo == hi) {
            t_[node] = a[lo];
            return;
        }
        int mid = lo + (hi - lo) / 2;
        build(2 * node, lo, mid, a);
        build(2 * node + 1, mid + 1, hi, a);
        t_[node] = std::min(t_[2 * node], t_[2 * node + 1]);
    }
 
    // BUG: 0 is used as the "no value here" answer. For min, 0 is not neutral.
    long long query(int node, int lo, int hi, int l, int r) const {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return t_[node];
        int mid = lo + (hi - lo) / 2;
        return std::min(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r));
    }
 
    int n_;
    std::vector<long long> t_;
};
 
int main() {
    MinTree mt({5, 3, 8, 6});
    std::cout << "min of [0,3]: " << mt.query(0, 3) << '\n';
    std::cout << "min of [2,3]: " << mt.query(2, 3) << '\n';
    std::cout << "min of [0,1]: " << mt.query(0, 1) << '\n';
}

The output is:

min of [0,3]: 3
min of [2,3]: 0
min of [0,1]: 0

The first line is right. The other two are wrong. The correct answers are 6 for [2,3], the smaller of 8 and 6, and 3 for [0,1], the smaller of 5 and 3.

This is the kind of bug that a whole-array test hides. The query on [0,3] is fully inside the root, so the function returns the root's stored value at once. The line that returns 0 never runs for that query. Only queries that touch a node outside their range reach the line.

Even a query on one position fails. The query on [0,0] returns 0, because the right half of the root lies outside the range and returns 0, and that 0 wins the minimum.

Look at what 0 does in a minimum. The answer for an outside node is combined with the answer for an inside node using std::min. If the outside node says 0, the minimum is at most 0, no matter what the inside values are. For [2,3], the answer is min(0, min(8, 6)), which is min(0, 6) = 0.

A neutral value is one that leaves the result unchanged when combined. The neutral value depends on the operation:

The fix changes the line that returns for an outside node:

    // For min, the neutral value is the largest possible number.
    long long query(int node, int lo, int hi, int l, int r) const {
        if (r < lo || hi < l) return std::numeric_limits<long long>::max();

The file also needs #include <limits>. The program then prints:

min of [0,3]: 3
min of [2,3]: 6
min of [0,1]: 3

Bug 3: lazy tags pushed in the wrong order

The third program supports two operations on an array of four values. assign(l, r, v) sets every value from position l to r to v. sum(l, r) adds up the values in that range. Each node has a lazy tag. A tag is an assignment that the node has received but not yet passed to its children. Before the code looks at a node's children, it must push the tag down to them, so that the children hold the right values.

#include <iostream>
#include <optional>
#include <vector>
 
// Range assign and range sum. A node's lazy tag is a value that the whole
// node should be set to, but its children have not been updated yet.
class AssignSumTree {
public:
    explicit AssignSumTree(int n) : n_(n), t_(4 * static_cast<size_t>(n)) {}
 
    void assign(int l, int r, long long v) { assign(1, 0, n_ - 1, l, r, v); }
 
    long long sum(int l, int r) { return sum(1, 0, n_ - 1, l, r); }
 
private:
    struct Node {
        long long total = 0;
        std::optional<long long> tag;
    };
 
    void apply(int node, int lo, int hi, long long v) {
        t_[node].total = v * (hi - lo + 1);
        t_[node].tag = v;
    }
 
    void push(int node, int lo, int hi) {
        if (!t_[node].tag) return;
        int mid = lo + (hi - lo) / 2;
        apply(2 * node, lo, mid, *t_[node].tag);
        apply(2 * node + 1, mid + 1, hi, *t_[node].tag);
        t_[node].tag.reset();
    }
 
    // BUG: the parent's pending tag is pushed after the children were changed.
    void assign(int node, int lo, int hi, int l, int r, long long v) {
        if (r < lo || hi < l) return;
        if (l <= lo && hi <= r) {
            apply(node, lo, hi, v);
            return;
        }
        int mid = lo + (hi - lo) / 2;
        assign(2 * node, lo, mid, l, r, v);
        assign(2 * node + 1, mid + 1, hi, l, r, v);
        push(node, lo, hi);
        t_[node].total = t_[2 * node].total + t_[2 * node + 1].total;
    }
 
    long long sum(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return t_[node].total;
        push(node, lo, hi);
        int mid = lo + (hi - lo) / 2;
        return sum(2 * node, lo, mid, l, r) + sum(2 * node + 1, mid + 1, hi, l, r);
    }
 
    int n_;
    std::vector<Node> t_;
};
 
int main() {
    AssignSumTree st(4);
    st.assign(0, 3, 5);
    st.assign(0, 1, 1);
    std::cout << "values:";
    for (int i = 0; i < 4; ++i) std::cout << ' ' << st.sum(i, i);
    std::cout << '\n';
    std::cout << "sum of [0,3]: " << st.sum(0, 3) << '\n';
}

The output is:

values: 5 5 5 5
sum of [0,3]: 20

The correct values after the two assignments are 1 1 5 5, with sum 12. The program is wrong.

Trace the calls. The first call, assign(0, 3, 5), covers the whole array, so the root receives the tag 5. The root's total is 20. Its children have no values yet.

The second call, assign(0, 1, 1), starts at the root. The root covers 0 to 3, and the request covers only 0 to 1, so the root is partly covered. The buggy code does the following, in this order:

1. It calls assign on the left child, which covers positions 0 to 1. That child is fully covered, so it stores the tag 1 and its total becomes 1 * 2 = 2.
2. It calls assign on the right child, which covers positions 2 to 3. That child is outside the request, so nothing happens.
3. It pushes the root's tag, 5, down to both children. The left child's total becomes 5 * 2 = 10 and its tag becomes 5. The right child's total becomes 10 and its tag becomes 5.

Step 3 overwrites the work from step 1. The left child's 1 is lost, and the children now say that positions 0 to 1 hold 5. The total is 20.

The fix is to push first. The tag must reach the children before the children are changed:

        push(node, lo, hi);  // push the old tag down before the children change
        int mid = lo + (hi - lo) / 2;
        assign(2 * node, lo, mid, l, r, v);
        assign(2 * node + 1, mid + 1, hi, l, r, v);
        t_[node].total = t_[2 * node].total + t_[2 * node + 1].total;

With this order, the children first receive 5 each. Then the left child receives the 1 for positions 0 to 1, and its total becomes 2. The root's total is 2 + 10 = 12. The program prints:

values: 1 1 5 5
sum of [0,3]: 12

The sanitizers did not report anything for this bug. Building the buggy program with -fsanitize=address,undefined gives the same two lines, and the program exits with code 0. A sanitizer finds memory errors and undefined behaviour. It does not know what answer you wanted. This bug is only found by comparing the output with a hand trace.

Finding a bug you cannot see

When the cause of a wrong answer is not clear, do not read the whole file again and again. Narrow the problem down in three steps.

First, write the slow answer. For a small array, a loop that tries every range gives the right answer. Compare the slow answer with the tree's answer for every pair of positions l and r, and print the first pair where they differ. This is the same idea as the brute-force check in the previous lesson, applied to a small array instead of random ones.

Second, make the input as small as the bug allows. Start with the failing array and remove values until the answer becomes right again. Bug 1 needs 6 values to fail, because 3 values still fit in 2 * n slots. Bug 2 needs only 2 values. With the array 5, 3, the query [0,0] returns 0 instead of 5. With the single value 5, every query is correct, because the root is a leaf and the outside branch never runs. A two-value input is small enough to trace on paper in a minute.

Third, print the path. Add one line at the top of the query function that prints node, lo, hi, l and r. Each printed line then shows which nodes the query visited and what each one returned. Compare the printed lines with your hand trace. Remove the print once the bug is fixed.

Common mistakes

Trusting a whole-array test. Bug 2 passes on [0,3]. A test set that only checks the whole array will miss bugs in the partial-range code. Test at least one query that starts inside the array and ends inside it, such as [1,2].

Sizing the vector by hand. Writing 2 * n because the tree has about 2n nodes is wrong. Bug 1 shows the exact failure. Use 4 * n, or the size of the next power of two times 2, which is also safe. A vector of size n fails even sooner. With 2 values, node 2 is already past the end of a 2-slot vector.

Using [] while debugging. A bad [] index does not throw. It may write into the memory of another object, and the program may crash later, far from the bad line. Use .at() while you find the bug, as Bug 1 does.

Pushing a tag after using the children. Any function that reads or writes a child must first push the parent's tag. This includes the sum query, the assign function and any update that changes both halves. Bug 3 shows the result of breaking this rule in the assign function.

Forgetting to clear a tag. After push sends a tag to the children, the parent's tag must be cleared. The code above does this with reset(). If the tag stayed, the same value would be pushed again on the next visit. For an add tag, the same amount would be added twice.

Practice

Exercise 1: does a size of 2n fail for 3 values?

Bug 1 uses t_(2 * a.size()). Does SumTree crash for the array 7, 8, 9? Explain using the largest node number.

Show the answer

No, it does not crash. For 3 values, the largest node number is 5. The vector has 2 * 3 = 6 slots, numbered 0 to 5, so node 5 fits. The program prints sum of all: 24. The crash in Bug 1 needs 6 values, and then the first node number past the end is 12.

Exercise 2: what does the minimum tree return for [1,2]?

Use the buggy MinTree from Bug 2 on the array 5, 3, 8, 6. What does query(1, 2) return? What should it return?

Show the answer

It returns 0. The root covers 0 to 3, so it is partly covered. The left child covers 0 to 1. Its leaf for position 0 is outside the request, so it returns 0. Its leaf for position 1 returns 3, and min(0, 3) is 0. The right child covers 2 to 3. Its leaf for position 2 returns 8, and its leaf for position 3 is outside, so it returns 0. The result is min(0, min(8, 0)) = 0. The correct answer is 3, the smallest of 3 and 8.

Exercise 3: predict the output after swapping the lines

In Bug 3, move the call push(node, lo, hi); above the two recursive calls, and leave the rest of the file unchanged. Before you run it, predict the two output lines.

Show the answer

The output is values: 1 1 5 5 and sum of [0,3]: 12. This is the same as the fixed version. The push runs first, so the children receive the 5 before the left child receives the 1.

Exercise 4: which sizes break 2 * n?

For a recursive tree of 6 values, the largest node number is 13. For 10 values, the largest node number is 25. Which of these two sizes does 2 * n fail for, and what does 4 * n give for each?

Show the answer

Both sizes fail. For 6 values, 2 * n is 12 slots, and the build reaches node 12, which is past the end. For 10 values, 2 * n is 20 slots, and node 25 is past the end. The value 4 * n gives 24 slots for 6 values and 40 slots for 10 values. Both are larger than the largest node number.

Exercise 5: why does the query on the whole array pass in Bug 2?

Explain why mt.query(0, 3) returns 3 with the buggy code, even though the query on [2,3] returns 0.

Show the answer

The query on [0,3] covers the whole root node. The first if in the query checks whether the node lies outside the range, and it does not. The second if checks whether the node lies inside the range, and it does. The function returns the root's stored minimum at once. The line that returns 0 never runs. The query on [2,3] is partly outside the root, so the function must visit children that lie outside the range, and those return 0.

Summary

• Size the node vector with 4 * n. The largest node number can be larger than 2 * n.
• For a query on a range with no positions, return the neutral value for the operation. It is 0 for a sum, 1 for a product, and the largest possible number for a minimum.
• A whole-array query can pass while partial queries fail. Test at least one query that starts and ends inside the array.
• Push a lazy tag to the children before you read or change them. Clear the tag after you push it.
• Sanitizers find memory errors. They do not find wrong answers, so compare the output with a hand trace.