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 $2i+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:

python
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


---

*Continue reading the full article on [TildAlice](https://tildalice.io/segment-tree-off-by-one-bugs-range-queries/)*