Segment Trees & Fenwick Trees

When a prefix sum isn’t enough

Prefix sums give O(1) range queries but O(n) updates. When values change between queries, you need a structure that does both query and update in O(log n). Two tools cover almost everything: the Fenwick tree (compact, prefix-sum-style) and the segment tree (general, any associative operation, plus range updates).

Fenwick tree (Binary Indexed Tree)

Compact and fast for invertible prefix aggregates (sums, counts). Each index is responsible for a range determined by its lowest set bit (i & -i):

class BIT:
    def __init__(self, n): self.tree = [0] * (n + 1)
    def update(self, i, delta):       # 1-indexed point update
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i               # jump to the next responsible index
    def query(self, i):               # prefix sum [1..i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    # range sum [l..r] = query(r) - query(l - 1)

O(log n) update and prefix query, O(n) space — and very small constants. Powers Range Sum Query – Mutable, Count of Smaller Numbers After Self, counting inversions, and 2-D variants. (Range update + point query: maintain a BIT over a difference array.)

Segment tree

More general — supports any associative combine (sum, min, max, gcd, or custom) and, with lazy propagation, range updates. Each node holds the aggregate of a segment; query and update walk O(log n) nodes:

class SegTree:
    def __init__(self, a):
        self.n = len(a)
        self.t = [0] * (2 * self.n)            # iterative, array-backed
        for i in range(self.n): self.t[self.n + i] = a[i]
        for i in range(self.n - 1, 0, -1):
            self.t[i] = self.t[2*i] + self.t[2*i + 1]   # combine = sum (swap for min/max)
    def update(self, i, val):
        i += self.n; self.t[i] = val
        while i > 1:
            i //= 2; self.t[i] = self.t[2*i] + self.t[2*i + 1]
    def query(self, l, r):                      # [l, r)
        res = 0; l += self.n; r += self.n
        while l < r:
            if l & 1: res += self.t[l]; l += 1
            if r & 1: r -= 1; res += self.t[r]
            l //= 2; r //= 2
        return res

Use it for Range Minimum/Max Query, range-sum with updates, gcd over ranges, and “count of elements in a range” (a merge-sort tree).

Lazy propagation (range updates)

For range updates (“add v to all of [l, r]”), storing the change at every leaf is O(n). Lazy propagation stores a pending update on internal nodes and pushes it down only when needed, keeping range-update and range-query at O(log n). It’s the tool for “range assign/add + range query” (“Range Module,” booking with overlaps, “falling squares”). More code, but the standard answer when both ranges mutate.

Other variants worth naming

• Merge-sort tree — each node stores its sorted subarray for “count values ≤ x in [l, r]” queries (O(log²n)).
• Sparse table — O(1) idempotent range queries (min/max/gcd) on a static array after O(n log n) build (no updates).
• 2-D BIT / segment tree — range queries on a grid.

Choosing

Pitfalls

• Reaching for a segment tree when a Fenwick (or prefix sum) suffices — match the tool to the query.
• Off-by-one / 1- vs 0-indexing — Fenwick is 1-indexed; keep conventions straight.
• Forgetting lazy push-down — range-update bugs come from not propagating pending updates before descending.

Choosing in an interview

Mutable array + range queries → BIT (sums) or segment tree (general); add lazy propagation the moment you also need range updates; static array → prefix sums or a sparse table.