Segment Tree Off-by-One: 5 Bugs That Break Range Queries

The Bug That Cost Me a Google Interview

My segment tree passed 47 out of 48 test cases. The failure? A range sum query that should’ve returned 15 returned 0 instead. After 20 minutes of panic-debugging during the interview, I found it: right_child = 2 * node + 1 instead of 2 * node + 2. That single digit turned a working solution into garbage.

Segment trees are deceptively simple until you hit the edge cases. The index arithmetic looks obvious on paper — left child at $2i$, right child at DOLLAR_AMOUNT_1i+1$ for 0-indexed nodes — but in practice, five specific bugs account for roughly 80% of all segment tree failures in coding interviews. I’ve debugged enough of these (both my own and in mock interviews) to recognize the patterns instantly now.

This post walks through the five most common off-by-one errors that silently corrupt segment trees, each with a minimal failing test case and the exact fix. No theory dumps — just the bugs you’ll actually encounter when the clock is ticking.

Bug #1: Wrong Child Index Calculation

The most common mistake, and the one that bit me in that Google interview. Here’s what the broken code looks like:

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)  # Safe upper bound for tree size
        self.build(arr, 0, 0, self.n - 1)

    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return

        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 1  # BUG: Should be 2 * node + 2

        self.build(arr, left_child, start, mid)
        self.build(arr, right_child, mid + 1, end)
        self.tree[node] = self.tree[left_child] + self.tree[right_child]

# Test case that exposes the bug
arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)
print(st.tree[:10])  # Corrupted tree structure

When you set both children to the same index, the tree structure degenerates. The right subtree overwrites the left subtree’s values during construction, and you end up with nonsense sums. The fix is trivial but easy to miss under pressure:

left_child = 2 * node + 1
right_child = 2 * node + 2  # Correct

Why does this happen? Because we’re juggling two different indexing schemes: the conceptual binary tree (where node 0 has children 1 and 2) and the array representation (0-indexed). The moment you type 2 * node, your brain wants to add 1 — but you need to add 1 for left and 2 for right.

Bug #2: Off-by-One in Range Query Bounds

This one’s subtle. Your segment tree builds correctly, but range queries return wrong results for edge cases. Here’s the broken query function:

def query(self, node, start, end, L, R):
    # Query sum in range [L, R]
    if R < start or L > end:  # No overlap
        return 0

    if L <= start and end <= R:  # Complete overlap
        return self.tree[node]

    mid = (start + end) // 2
    left_sum = self.query(2 * node + 1, start, mid, L, R)
    right_sum = self.query(2 * node + 2, mid, end, L, R)  # BUG: mid should be mid + 1
    return left_sum + right_sum

# Failing test case
arr = [1, 2, 3, 4, 5]
st = SegmentTree(arr)
result = st.query(0, 0, 4, 2, 4)  # Query sum of arr[2:5] -> should be 12
print(result)  # Wrong answer, likely double-counts arr[2]

The bug is in how you split the range. When you recurse on the right child, the range should be [mid + 1, end], not [mid, end]. Otherwise, the element at index mid gets counted by both children in certain queries.

Here’s the fix:

mid = (start + end) // 2
left_sum = self.query(2 * node + 1, start, mid, L, R)
right_sum = self.query(2 * node + 2, mid + 1, end, L, R)  # Correct
return left_sum + right_sum

The mental model that helps: at each node, you’re dividing the range into two disjoint halves. Left gets [start, mid], right gets [mid + 1, end]. There’s no overlap. If you pass [mid, end] to the right child, you’re asking it to consider mid twice.

Bug #3: Wrong Midpoint Calculation with Large Indices

This is the classic integer overflow trap, though in Python it manifests differently than in C++. The issue isn’t overflow (Python handles big ints fine) but rather incorrect midpoint logic when you’re working with large index ranges:

mid = (start + end) // 2  # Looks fine, but...

In languages like C++ or Java, if start and end are close to INT_MAX, start + end overflows before the division. The standard fix is:

mid = start + (end - start) // 2  # Overflow-safe

Python doesn’t overflow, but there’s still a gotcha: if you’re porting segment tree code from C++ and you forget to adjust integer division semantics. In Python 3, // is floor division, which handles negatives correctly. But if you accidentally use / (float division) and then cast to int, you’ll get wrong midpoints for negative indices (rare in segment trees, but possible in coordinate compression scenarios).

But here’s where I’m not entirely sure: I’ve never actually hit this bug in a pure Python segment tree implementation because (a) Python’s arbitrary-precision integers don’t overflow, and (b) most coding interview problems use array sizes under $10^5$, nowhere near overflow territory. The bigger risk is copy-pasting the (start + end) // 2 pattern from C++ solutions without thinking.

Bug #4: Incorrect Update Propagation in Point Updates

Point update seems straightforward: find the leaf, change its value, then propagate the change up to the root. But there’s a classic mistake in the propagation step:

def update(self, node, start, end, idx, val):
    if start == end:
        self.tree[node] = val  # Update leaf
        return

    mid = (start + end) // 2
    if idx <= mid:
        self.update(2 * node + 1, start, mid, idx, val)
    else:
        self.update(2 * node + 2, mid + 1, end, idx, val)

    # BUG: Forgot to update current node after recursion
    # self.tree[node] should be recomputed here

# Correct version:
def update(self, node, start, end, idx, val):
    if start == end:
        self.tree[node] = val
        return

    mid = (start + end) // 2
    if idx <= mid:
        self.update(2 * node + 1, start, mid, idx, val)
    else:
        self.update(2 * node + 2, mid + 1, end, idx, val)

    # Recompute current node's value from children
    self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

This bug is insidious because the first update might seem to work — you change the leaf, and if you query that exact leaf, you get the right answer. But any query that involves an ancestor node returns stale data. The fix is mechanical: after every recursive update call, recompute the current node’s value from its children.

Time complexity stays $O(\log n)$ per update because you’re touching one node per level of the tree. The recomputation at each level is $O(1)$.

Bug #5: Fencepost Error in Range Update with Lazy Propagation

Lazy propagation adds a layer of complexity: instead of updating every node in a range immediately, you mark nodes as “dirty” and defer updates until necessary. The classic bug is in how you check for complete vs partial overlap:

def range_update(self, node, start, end, L, R, val):
    # Apply any pending updates first
    if self.lazy[node] != 0:
        self.tree[node] += (end - start + 1) * self.lazy[node]
        if start != end:  # Not a leaf
            self.lazy[2 * node + 1] += self.lazy[node]
            self.lazy[2 * node + 2] += self.lazy[node]
        self.lazy[node] = 0

    if R < start or L > end:  # No overlap
        return

    if L <= start and end <= R:  # Complete overlap
        self.tree[node] += (end - start + 1) * val
        if start != end:
            self.lazy[2 * node + 1] += val
            self.lazy[2 * node + 2] += val
        return

    # Partial overlap - recurse
    mid = (start + end) // 2
    self.range_update(2 * node + 1, start, mid, L, R, val)
    self.range_update(2 * node + 2, mid + 1, end, L, R, val)  # BUG CHECK: Is this mid or mid + 1?
    self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

The bug here is usually not in the recursion itself (that’s the same as Bug #2) but in the lazy propagation formula:

self.tree[node] += (end - start + 1) * val

Why + 1? Because the range [start, end] is inclusive on both ends. If start = 2 and end = 5, there are 4 elements, not 3. The number of elements in an inclusive range $[a, b]$ is $b – a + 1$. Forgetting the + 1 means your range updates are systematically too small.

Here’s a test case that catches it:

arr = [0, 0, 0, 0, 0]  # All zeros
st = LazySegmentTree(arr)
st.range_update(0, 0, 4, 1, 3, 5)  # Add 5 to arr[1:4]
result = st.query(0, 0, 4, 0, 4)  # Total sum should be 15
print(result)  # Will be 10 if you forgot the + 1

If you use (end - start) * val instead of (end - start + 1) * val, the test fails.

Complete Working Implementation

Here’s a full segment tree with all five bugs fixed, plus a lazy propagation variant. This is runnable code you can paste into LeetCode or Codeforces:

class SegmentTree:
    """Range sum segment tree with point updates."""

    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        if arr:
            self.build(arr, 0, 0, self.n - 1)

    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return

        mid = start + (end - start) // 2  # Overflow-safe
        left_child = 2 * node + 1
        right_child = 2 * node + 2

        self.build(arr, left_child, start, mid)
        self.build(arr, right_child, mid + 1, end)
        self.tree[node] = self.tree[left_child] + self.tree[right_child]

    def update(self, idx, val):
        self._update(0, 0, self.n - 1, idx, val)

    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return

        mid = start + (end - start) // 2
        if idx <= mid:
            self._update(2 * node + 1, start, mid, idx, val)
        else:
            self._update(2 * node + 2, mid + 1, end, idx, val)

        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def query(self, L, R):
        return self._query(0, 0, self.n - 1, L, R)

    def _query(self, node, start, end, L, R):
        if R < start or L > end:
            return 0

        if L <= start and end <= R:
            return self.tree[node]

        mid = start + (end - start) // 2
        left_sum = self._query(2 * node + 1, start, mid, L, R)
        right_sum = self._query(2 * node + 2, mid + 1, end, L, R)
        return left_sum + right_sum


class LazySegmentTree:
    """Segment tree with lazy propagation for range updates."""

    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        if arr:
            self.build(arr, 0, 0, self.n - 1)

    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return

        mid = start + (end - start) // 2
        self.build(arr, 2 * node + 1, start, mid)
        self.build(arr, 2 * node + 2, mid + 1, end)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def push(self, node, start, end):
        """Push down lazy value to children."""
        if self.lazy[node] != 0:
            self.tree[node] += (end - start + 1) * self.lazy[node]
            if start != end:
                self.lazy[2 * node + 1] += self.lazy[node]
                self.lazy[2 * node + 2] += self.lazy[node]
            self.lazy[node] = 0

    def range_update(self, L, R, val):
        self._range_update(0, 0, self.n - 1, L, R, val)

    def _range_update(self, node, start, end, L, R, val):
        self.push(node, start, end)

        if R < start or L > end:
            return

        if L <= start and end <= R:
            self.tree[node] += (end - start + 1) * val
            if start != end:
                self.lazy[2 * node + 1] += val
                self.lazy[2 * node + 2] += val
            return

        mid = start + (end - start) // 2
        self._range_update(2 * node + 1, start, mid, L, R, val)
        self._range_update(2 * node + 2, mid + 1, end, L, R, val)

        # Don't forget to push children before reading their values
        self.push(2 * node + 1, start, mid)
        self.push(2 * node + 2, mid + 1, end)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def query(self, L, R):
        return self._query(0, 0, self.n - 1, L, R)

    def _query(self, node, start, end, L, R):
        self.push(node, start, end)

        if R < start or L > end:
            return 0

        if L <= start and end <= R:
            return self.tree[node]

        mid = start + (end - start) // 2
        left_sum = self._query(2 * node + 1, start, mid, L, R)
        right_sum = self._query(2 * node + 2, mid + 1, end, L, R)
        return left_sum + right_sum


# Test cases
if __name__ == "__main__":
    # Basic segment tree test
    arr = [1, 3, 5, 7, 9, 11]
    st = SegmentTree(arr)

    print("Original array:", arr)
    print("Sum [1, 4]:", st.query(1, 4))  # Should be 3 + 5 + 7 + 9 = 24

    st.update(3, 10)  # Change arr[3] from 7 to 10
    print("After update arr[3] = 10:")
    print("Sum [1, 4]:", st.query(1, 4))  # Should be 3 + 5 + 10 + 9 = 27

    # Lazy propagation test
    arr2 = [0, 0, 0, 0, 0]
    lazy_st = LazySegmentTree(arr2)

    lazy_st.range_update(1, 3, 5)  # Add 5 to arr[1:4]
    print("\nAfter range update [1, 3] += 5:")
    print("Sum [0, 4]:", lazy_st.query(0, 4))  # Should be 15
    print("Sum [1, 3]:", lazy_st.query(1, 3))  # Should be 15
    print("Sum [0, 1]:", lazy_st.query(0, 1))  # Should be 5

Output:

Original array: [1, 3, 5, 7, 9, 11]
Sum [1, 4]: 24
After update arr[3] = 10:
Sum [1, 4]: 27

After range update [1, 3] += 5:
Sum [0, 4]: 15
Sum [1, 3]: 15
Sum [0, 1]: 5

Complexity Analysis and When to Actually Use This

Segment trees give you $O(\log n)$ for both range queries and point updates, which beats the naive $O(n)$ scan. But here’s the thing: for small arrays (say, $n < 1000$), the constant factors make segment trees slower than just summing in a loop. I’d reach for a segment tree when:

1. Multiple range queries on static or slowly-changing data: If you’re doing 10,000 queries on an array that only updates occasionally, segment tree wins.
2. Range updates + range queries: Lazy propagation handles this in $O(\log n)$ per operation. Alternatives like Fenwick trees can’t do range updates efficiently.
3. Non-invertible operations: If your operation isn’t easily reversible (like min/max/GCD), segment trees handle it. For sums, you can use a Fenwick tree, which has better constants.

Space complexity is $O(4n)$ for the tree array. In practice, 4 * n is a safe upper bound — the exact size is $2^{\lceil \log_2 n \rceil + 1} – 1$, but that’s annoying to compute. Just allocate 4 * n and move on.

One thing I haven’t fully tested: how segment trees perform when $n$ is huge ($10^7$or more) and you're memory-constrained. My guess is that cache misses start dominating, and a simpler data structure might win despite worse asymptotic complexity. But take that with a grain of salt — I've only benchmarked up to$n = 10^6$ on my M1 MacBook.

The Interview Debugging Checklist

When your segment tree fails a test case mid-interview:

1. Check child indices: 2 * node + 1 and 2 * node + 2? Not both + 1?
2. Check range splits: Right child starts at mid + 1, not mid?
3. Check range size: Using end - start + 1 for inclusive ranges, not end - start?
4. Check update propagation: Are you recomputing parent nodes after updates?
5. Print the tree array: Sometimes seeing [0, 27, 4, 23, ...] reveals the structure is broken.

And if you’re stuck, rebuild from scratch. Seriously. I’ve wasted 10 minutes trying to debug a segment tree only to realize I’d been staring at a typo the whole time. Rewriting from memory takes 3 minutes and forces you to think through each line.

FAQ

Q: When should I use a Fenwick tree instead of a segment tree?

For range sum queries with point updates, Fenwick trees are faster (better constant factors, simpler code). Use segment trees when you need range updates, non-invertible operations (min/max/GCD), or when you’re already comfortable with the implementation and don’t want to learn another data structure mid-interview.

Q: How do I debug a segment tree that returns wrong answers only on edge cases?

Print the internal tree array and manually trace one failing query. Check: (1) Is the tree built correctly? Compare leaf values to the original array. (2) Are you handling single-element ranges [i, i] correctly? (3) Are you handling full-array queries [0, n-1] correctly? Nine times out of ten, it’s a range boundary issue (Bug #2 or Bug #5).

Q: Can I use 1-indexed nodes to avoid the +1/+2 confusion?

Yes, and many competitive programmers do. With 1-indexing, left child is 2 * node, right child is 2 * node + 1, which feels more symmetric. The tradeoff: you waste tree[0] and need to adjust your array indexing logic. I prefer 0-indexing because it matches Python’s default, but if 1-indexing clicks for you, go for it.

When Not to Overthink It

If you’re in an interview and the problem is just “find range sums,” consider whether you even need a segment tree. If there are no updates, a prefix sum array solves it in $O(1)$ per query with $O(n)$ preprocessing:

prefix = [0]
for x in arr:
    prefix.append(prefix[-1] + x)

# Range sum [L, R]
range_sum = prefix[R + 1] - prefix[L]

No index arithmetic, no edge cases, no bugs. Save the segment tree for when you actually need the extra power.

Debugging these five bugs late at night? Might be time for some Dark Chocolate Espresso Beans — the actual MVP of coding interview prep.

The real lesson: segment trees aren’t hard because the algorithm is complicated. They’re hard because there are five places where a single character difference (+1 vs +2, mid vs mid+1) turns correct code into silent failure. Write test cases that hit every edge: single-element arrays, full-range queries, boundary updates. And when in doubt, rebuild from scratch rather than debugging in circles.