Segment Tree and Fenwick Tree (BIT) Interview Patterns
These data structures answer range queries (sum, min, max) and support point updates in O(log N) time. They appear in competitive programming and occasionally in senior engineering interviews, especially for problems involving range queries with updates.
When to Use
- Range sum with point updates: Fenwick Tree (Binary Indexed Tree) — simpler code
- Range min/max queries: Segment Tree — Fenwick cannot do min/max
- Range updates + range queries: Segment Tree with lazy propagation
- Static range min/max (no updates): Sparse Table — O(1) query, O(N log N) build
Fenwick Tree (Binary Indexed Tree)
class BIT:
def __init__(self, n):
self.tree = [0] * (n + 1)
def update(self, i, delta):
while i 0:
s += self.tree[i]
i -= i & (-i) # remove lowest set bit
return s
def range_query(self, l, r):
return self.query(r) - self.query(l - 1)
Time: O(log N) per update and query. Space: O(N). The bit manipulation i & (-i) isolates the lowest set bit — the core of BIT’s efficiency. Index is 1-based.
Segment Tree (Range Sum)
class SegTree:
def __init__(self, nums):
self.n = len(nums)
self.tree = [0] * (4 * self.n)
self._build(nums, 0, 0, self.n - 1)
def _build(self, nums, node, start, end):
if start == end:
self.tree[node] = nums[start]
else:
mid = (start + end) // 2
self._build(nums, 2*node+1, start, mid)
self._build(nums, 2*node+2, mid+1, end)
self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
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+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, node, start, end, l, r):
if r < start or end < l: return 0
if l <= start and end <= r: return self.tree[node]
mid = (start + end) // 2
return (self.query(2*node+1, start, mid, l, r) +
self.query(2*node+2, mid+1, end, l, r))
Segment Tree with Lazy Propagation
For range updates (add 5 to all elements in [l, r]), propagate the update lazily: mark the node with the pending update and only push it down when a child is actually accessed. This reduces O(N) range updates to O(log N).
def push_down(self, node):
if self.lazy[node] != 0:
for child in [2*node+1, 2*node+2]:
self.tree[child] += self.lazy[node]
self.lazy[child] += self.lazy[node]
self.lazy[node] = 0
Sparse Table (Static Range Min)
def build_sparse_table(arr):
n = len(arr)
LOG = n.bit_length()
sparse = [[0]*n for _ in range(LOG)]
sparse[0] = arr[:]
for j in range(1, LOG):
for i in range(n - (1 << j) + 1):
sparse[j][i] = min(sparse[j-1][i], sparse[j-1][i + (1 << (j-1))])
return sparse
def rmq(sparse, l, r):
length = r - l + 1
k = length.bit_length() - 1
return min(sparse[k][l], sparse[k][r - (1 << k) + 1])
Build: O(N log N). Query: O(1). Works for idempotent operations (min, max, GCD) only — overlapping ranges are fine because min(a, a) = a.
Interview Problem Examples
- Range Sum Query — Mutable (LeetCode 307): use Fenwick Tree or Segment Tree
- Count of Smaller Numbers After Self (LeetCode 315): process right to left, BIT indexed by value
- Range Min Query (static): Sparse Table for O(1) queries
- Falling Squares (LeetCode 699): Segment Tree with coordinate compression
Interview Tips
- Fenwick Tree = simpler code, only for prefix sum. Segment Tree = more general.
- BIT is 1-indexed — off-by-one errors are common; test with small arrays.
- 4*N array size for segment tree is safe (prevents index out of bounds).
- Coordinate compression: map large value ranges to indices before building the tree.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use a Fenwick Tree vs a Segment Tree?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Fenwick Tree (BIT): use for prefix sum queries with point updates. It supports only operations where you can compute a range query from two prefix queries (sum, XOR, count). Cannot handle range min/max. Code is shorter (5-10 lines). Constant factor is small. Segment Tree: use when you need range min, range max, or range updates (lazy propagation). Also needed for non-prefix-decomposable queries. More code to write and debug under interview pressure. Decision flowchart: (1) Do you need range min or max? → Segment Tree. (2) Do you need range updates (not just point updates)? → Segment Tree with lazy propagation. (3) Do you need only range sum or range XOR with point updates? → Fenwick Tree (simpler). (4) Static array, range min/max, no updates? → Sparse Table (O(1) query after O(N log N) build). In interviews, BIT is preferred when it applies because it is faster to code correctly.” }
},
{
“@type”: “Question”,
“name”: “How does the Fenwick Tree use bit manipulation to achieve O(log N) operations?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “The BIT's clever bit manipulation is: i & (-i), which isolates the lowest set bit of i. In two's complement, -i flips all bits and adds 1, so i & (-i) gives only the lowest set bit. For update(i, delta): start at index i, add delta, then advance to i + (i & -i) — this moves to the next "responsible" index that covers i. For query(i) (prefix sum 1..i): start at i, add tree[i], then go to i – (i & -i) — this strips the lowest set bit, moving to the largest index less than i that covers a disjoint range. The BIT logically partitions [1..N] into intervals of power-of-2 lengths. Each index i stores the sum of a specific interval ending at i. The interval length is i & -i. Example: index 6 (binary 110) has lowest bit 2, so tree[6] stores sum of 2 elements: [5,6]. Update and query each touch O(log N) indices.” }
},
{
“@type”: “Question”,
“name”: “How do you use a Fenwick Tree to count inversions in an array?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Counting inversions with a BIT: process the array from right to left. For each element arr[i], query the BIT for the count of elements already seen (to the right of i) that are less than arr[i] — this gives the number of inversions involving arr[i] on the left. Then update the BIT at position arr[i]. Coordinate compression: since arr values may be large, compress them to ranks [1..N] before indexing the BIT. Algorithm: compress values → process right to left → for each value v, inversions += BIT.query(v-1) (count of smaller elements already seen); then BIT.update(v, 1). Total inversions is the sum. Time: O(N log N) — N elements, each with O(log N) BIT operations. Space: O(N). This is a classic BIT application: "count elements satisfying a condition in a range processed so far."” }
}
]
}