Segment Tree and Range Query Patterns: Fenwick Tree, Lazy Propagation, Order Statistics

By /

Segment Tree and Range Query Interview Patterns

Segment trees solve range query problems — finding the sum, min, max, or GCD over an array interval — with O(log n) query and update time. They appear in hard LeetCode problems and senior-level interviews at companies that care about algorithmic depth. This guide covers the implementation and the pattern recognition needed to apply them correctly.

When to Use a Segment Tree

Use a segment tree when you need both:

  • Range queries: sum/min/max/GCD over array[i..j]
  • Point updates: update a single element

Complexity: O(n) build, O(log n) query and update. Prefix sum arrays are O(1) query but O(n) update. Segment trees are the right tool when you need both operations to be fast.

Implementation: Sum Segment Tree

class SegmentTree:
    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, idx, val, node=0, start=0, end=None):
        if end is None: end = self.n - 1
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) // 2
        if idx <= mid: self.update(idx, val, 2*node+1, start, mid)
        else:          self.update(idx, val, 2*node+2, mid+1, end)
        self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]

    def query(self, l, r, node=0, start=0, end=None):
        if end is None: end = self.n - 1
        if r < start or end < l: return 0          # out of range
        if l <= start and end <= r: return self.tree[node]  # fully covered
        mid = (start + end) // 2
        return (self.query(l, r, 2*node+1, start, mid) +
                self.query(l, r, 2*node+2, mid+1, end))

Range Sum Query – Mutable (LeetCode 307)

class NumArray:
    def __init__(self, nums):
        self.st = SegmentTree(nums)

    def update(self, index, val):
        self.st.update(index, val)

    def sumRange(self, left, right):
        return self.st.query(left, right)

Binary Indexed Tree (Fenwick Tree) — Simpler for Range Sum

When you only need range sum + point update (not min/max/other operations), the Fenwick tree is simpler to implement:

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):  # i is 1-indexed
        while i  0:
            s += self.tree[i]
            i -= i & (-i)        # remove lowest set bit
        return s

    def range_sum(self, l, r):
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

Fenwick tree uses O(n) space (vs. O(4n) for segment tree), has simpler code, but only supports commutative/invertible operations (sum, XOR). Use segment tree for min/max.

Count of Smaller Numbers After Self (LeetCode 315)

For each element, count how many elements to its right are smaller. Use a Fenwick tree over value coordinates:

def count_smaller(nums):
    # Coordinate compress: map values to [1..n]
    sorted_unique = sorted(set(nums))
    rank = {v: i+1 for i, v in enumerate(sorted_unique)}
    n = len(nums)
    bit = BIT(len(sorted_unique))
    result = []
    for num in reversed(nums):
        r = rank[num]
        result.append(bit.prefix_sum(r - 1))  # count elements with rank < r
        bit.update(r, 1)                        # register this element
    return result[::-1]

Lazy Propagation (Range Update)

When you need range updates (add 5 to all elements in [l..r]) and range queries, use lazy propagation to defer updates:

# Standard segment tree pushes updates down to children only when queried.
# lazy[node] stores a pending update not yet applied to children.
# On query/update reaching a node with lazy != 0:
#   1. Apply lazy to node value
#   2. Push lazy to children: lazy[2*node+1] += lazy[node]; lazy[2*node+2] += lazy[node]
#   3. Clear: lazy[node] = 0
# This keeps range update at O(log n) instead of O(n).

Common Problems by Pattern

Problem Type Tool LeetCode
Range sum, point update Fenwick tree 307, 315, 327
Range min/max, point update Segment tree 699, 715, 2407
Range update, range query Segment tree + lazy 732, 1505
Order statistics (kth smallest) Segment tree on values 315, 493, 2426

Interview Tips

  • Implement Fenwick tree for range sum — it is 15 lines vs. 40+ for segment tree and impresses interviewers with conciseness
  • The lowbit trick i & (-i) is the key to the Fenwick tree — explain it: -i in two's complement flips all bits and adds 1, leaving only the lowest set bit
  • When asked about range min/max, pivot to segment tree and explain why Fenwick doesn't work (min is not invertible)
  • For the coordinate compression pattern (used in 315, 327, 493) — sorting values and mapping to ranks is a powerful technique beyond segment trees

  • Atlassian Interview Guide
  • Coinbase Interview Guide
  • LinkedIn Interview Guide
  • Apple Interview Guide
  • Databricks Interview Guide
  • Meta Interview Guide
    • Scroll to Top