Segment Tree and Fenwick Tree Interview Patterns: Range Queries and Updates

By /
⏱ 5 min read

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.

  • Coinbase Interview Guide
  • Uber Interview Guide
  • LinkedIn Interview Guide
  • Databricks Interview Guide
  • Apple Interview Guide
  • Meta Interview Guide

    • 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.
    Scroll to Top