Segment Trees & Fenwick Trees

The range query problem#

You have an array of numbers — daily sales, scores, sensor readings — and must handle a stream of two operations:

• Query: what's the sum (or min/max) of elements from index l to r?
• Update: change the value at index i.

With 100,000 queries and updates on 100,000 elements, O(n) per operation means ~10¹⁰ steps; O(log n) means ~3.4 million. That's the difference between timing out and finishing instantly.

Segment trees#

A segment tree is a binary tree where each node stores the answer (e.g. the sum) for a segment of the array. The root covers the whole array, its children cover each half, and the leaves are single elements.

array:   [5, 3, 7, 9, 6, 4, 1, 2]

                     [0..7] = 37
               ┌──────────┴──────────┐
          [0..3] = 24           [4..7] = 13
          ┌────┴────┐           ┌────┴────┐
     [0..1]=8   [2..3]=16   [4..5]=10   [6..7]=3
      ┌─┴─┐       ┌─┴─┐       ┌─┴─┐       ┌─┴─┐
      5   3       7   9       6   4       1   2

• Query sum(2..5): combine the nodes that exactly cover the range — [2..3] = 16 and [4..5] = 10 → 26. At most O(log n) nodes are visited.
• Update index 3: change the leaf, then fix each ancestor on the way up — O(log n) nodes.

A compact iterative implementation#

Store the tree in an array of size 2n: leaves at positions n..2n-1, and each internal node i has children 2i and 2i + 1.

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * self.n + list(data)          # leaves live in the second half
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, value):
        i = index + self.n
        self.tree[i] = value
        while i > 1:                                   # walk up, recomputing parents
            i //= 2
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, left, right):
        """Sum of data[left..right], inclusive."""
        total = 0
        lo, hi = left + self.n, right + self.n + 1
        while lo < hi:
            if lo & 1:                                 # lo is a right child: take it, move right
                total += self.tree[lo]
                lo += 1
            if hi & 1:                                 # hi is a right child: take its left sibling
                hi -= 1
                total += self.tree[hi]
            lo //= 2
            hi //= 2
        return total

sales = [5, 3, 7, 9, 6, 4, 1, 2]
st = SegmentTree(sales)
print("sum(2..5) =", st.query(2, 5))
st.update(3, 0)                        # day 3's sales corrected from 9 to 0
print("sum(2..5) =", st.query(2, 5))
print("sum(0..7) =", st.query(0, 7))

Output:

sum(2..5) = 26
sum(2..5) = 17
sum(0..7) = 28

Segment trees are flexible: replace + with min, max or gcd to answer those range queries instead. Advanced versions add lazy propagation to update whole ranges in O(log n).

Fenwick trees (Binary Indexed Trees)#

A Fenwick tree (or Binary Indexed Tree, BIT) answers prefix sums with updates in O(log n) using a single array of size n + 1 and a clever bit trick. It's shorter to write and uses less memory than a segment tree, but it's mainly suited to operations that can be "subtracted", like sums.

Each index i (1-based) stores the sum of a block of elements whose length is the lowest set bit of i (i & -i — see the Bit Manipulation lesson):

• Prefix sum(i): add tree[i], then jump to i - (i & -i), until 0.
• Update(i, delta): add delta to tree[i], then jump to i + (i & -i), until past n.

class FenwickTree:
    def __init__(self, n):
        self.tree = [0] * (n + 1)                       # 1-based indexing

    def add(self, index, delta):                        # index is 0-based for callers
        i = index + 1
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i                                 # move to the next responsible node

    def prefix_sum(self, index):                        # sum of data[0..index]
        i, total = index + 1, 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i                                 # strip the lowest set bit
        return total

    def range_sum(self, left, right):
        return self.prefix_sum(right) - (self.prefix_sum(left - 1) if left else 0)

sales = [5, 3, 7, 9, 6, 4, 1, 2]
bit = FenwickTree(len(sales))
for i, value in enumerate(sales):
    bit.add(i, value)

print("sum(2..5) =", bit.range_sum(2, 5))
bit.add(3, -9)                         # set index 3 from 9 to 0 by adding the difference
print("sum(2..5) =", bit.range_sum(2, 5))
print("sum(0..7) =", bit.range_sum(0, 7))

Output:

sum(2..5) = 26
sum(2..5) = 17
sum(0..7) = 28

Same answers as the segment tree, in about half the code.

Segment tree vs Fenwick tree#

Rule of thumb: use a Fenwick tree for sums and counts; use a segment tree when you need min/max or more complex range operations.

Where you'll see them#

• Competitive programming and interviews: "Range Sum Query – Mutable", "Count of Smaller Numbers After Self" (BIT over ranks), counting inversions.
• Leaderboards and rankings: count how many scores fall below a value as scores change.
• Time-series analytics: sums over time windows with corrections.
• Databases and games: range aggregates, collision and interval queries (with related structures such as interval trees).

Common mistakes#

• Mixing 0-based and 1-based indices in Fenwick trees — index 0 would loop forever since 0 & -0 == 0.
• Using add(i, new_value) in a BIT when you mean "set" — add the difference instead.
• Off-by-one in inclusive/exclusive ranges — document which you use.
• Reaching for these structures when prefix sums suffice — if there are no updates, a prefix-sum array gives O(1) queries.

Key takeaways#

• Range queries with updates need O(log n) structures; prefix sums only work for static data.
• Segment trees store aggregates of segments and support sum, min, max and more.
• Fenwick trees use i & -i jumps for compact, fast prefix sums.
• Choose Fenwick for sums; segment trees for richer range operations.