Segment Trees and Fenwick Tree — Complete Interview Guide

Why Range Query Structures?

Naive array: O(n) per query, O(1) update
Prefix sums: O(1) query, O(n) update (breaks on mutation)
Segment Tree / BIT: O(log n) for both query and update

These structures are the difference between a correct solution and a timeout at Google and Amazon.

Binary Indexed Tree (Fenwick Tree)

The simplest structure for prefix sum queries with point updates. Encodes partial sums indexed by the lowest set bit of each index — a clever use of i & (-i).

BIT Operations

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)   # 1-indexed
 
    def update(self, i, delta):
        # Walk forward: each position is responsible for a range of size i & (-i)
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)   # jump to next ancestor
 
    def query(self, i):
        # Accumulate prefix sum [1..i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)   # jump to left boundary
        return s
 
    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

BIT Trick: `i & (-i)` isolates the lowest set bit

Update: add i & (-i) to move to the next responsible ancestor
Query: subtract i & (-i) to accumulate prefix sums left to right

Segment Tree

More powerful: supports any associative operation (min, max, GCD, etc.) and range updates with lazy propagation.

Simple Segment Tree

class SegTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (4 * n)   # always allocate 4*n nodes
 
    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, 2*node, start, mid)
            self.build(arr, 2*node+1, mid+1, end)
            self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
 
    def update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if idx <= mid:
                self.update(2*node, start, mid, idx, val)
            else:
                self.update(2*node+1, mid+1, end, idx, val)
            self.tree[node] = self.tree[2*node] + self.tree[2*node+1]  # re-aggregate
 
    def query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0    # out of range: return identity element
        if l <= start and end <= r:
            return self.tree[node]   # complete overlap
        mid = (start + end) // 2
        return (self.query(2*node, start, mid, l, r) +
                self.query(2*node+1, mid+1, end, l, r))

Lazy Propagation (Range Updates)

def push_down(self, node, start, end):
    if self.lazy[node] != 0:
        mid = (start + end) // 2
        # Push pending update to both children
        self.tree[2*node] += self.lazy[node] * (mid - start + 1)
        self.tree[2*node+1] += self.lazy[node] * (end - mid)
        self.lazy[2*node] += self.lazy[node]
        self.lazy[2*node+1] += self.lazy[node]
        self.lazy[node] = 0   # clear after pushing down

Complexity Reference

Structure	Build	Point Update	Range Query	Range Update
BIT	O(n)	O(log n)	O(log n)	—
Segment Tree	O(n)	O(log n)	O(log n)	O(log n) with lazy

When to Use What

Scenario	Use
Prefix sums only (immutable)	Prefix sum array
Point update + prefix sum	BIT (Fenwick Tree)
Range update + range query	Segment Tree + lazy propagation
Min/max range query	Segment Tree
2D range sum	2D BIT
Range add, point query	BIT with difference array
Count inversions	BIT + coordinate compression

2D BIT Template

class BIT2D:
    def __init__(self, m, n):
        self.m, self.n = m, n
        self.tree = [[0] * (n + 1) for _ in range(m + 1)]
 
    def update(self, r, c, delta):
        i = r
        while i <= self.m:
            j = c
            while j <= self.n:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)
 
    def query(self, r, c):
        s = 0
        i = r
        while i > 0:
            j = c
            while j > 0:
                s += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return s

Problem Index

#	Problem	Structure	Difficulty
01	Range Sum Query Mutable	BIT / Seg Tree	Medium
02	Count of Smaller Numbers After Self	BIT / Merge Sort	Hard
03	Count of Range Sum	Merge Sort / BIT	Hard
04	Queue Reconstruction (revisit)	BIT order	Medium
05	Reverse Pairs	BIT / Merge Sort	Hard
06	Range Sum Query 2D Mutable	2D BIT	Hard
07	My Calendar I, II, III	Segment Tree / Sorted	Medium/Hard
08	Falling Squares	Coordinate compress + Seg Tree	Hard
09	Rectangle Area II	Coordinate compression	Hard
10	Number of Longest Increasing Subsequence	Seg Tree on LIS	Medium
11	Max Sum of Rectangle No Larger Than K	BIT + prefix	Hard
12	Longest Increasing Subsequence	Seg Tree on value	Medium
13	Shifting Letters II	Difference Array + BIT	Medium
14	Stamping the Grid	Prefix sums 2D	Hard
15	Segment Trees and BIT Master Recap	Cheatsheet	—

Key Takeaways

When an array is mutable and you need repeated range queries, prefix sums break down — use a BIT or Segment Tree.
BIT uses i & (-i) (lowest set bit) to define the range each position is responsible for; this enables O(log n) updates and prefix queries.
Segment Tree stores aggregates at every level of a binary split — each node covers a contiguous subrange and combines two children.
Always allocate 4*n nodes for a Segment Tree to safely handle arbitrary (non-power-of-two) array sizes.
Lazy propagation defers range updates until a node's children are actually accessed — this keeps range-update complexity at O(log n).
BIT cannot handle non-invertible queries (like range minimum) — you need a Segment Tree for those.
2D BIT extends the lowest-set-bit idea to two dimensions for rectangle sum queries in O(log m * log n).

Why Range Query Structures?#

Binary Indexed Tree (Fenwick Tree)#

BIT Operations#

BIT Trick: i & (-i) isolates the lowest set bit#

Segment Tree#

Simple Segment Tree#

Lazy Propagation (Range Updates)#

Complexity Reference#

When to Use What#

2D BIT Template#

Problem Index#

Key Takeaways#

Related reading