Segment Tree and Fenwick Tree Interview Patterns: Range Queries, Lazy Propagation, and BIT (2025)

By /
⏱ 6 min read

Binary Indexed Tree (Fenwick Tree / BIT)

A BIT supports prefix sum queries and point updates in O(log n) time with O(n) space. Simpler to implement than a segment tree. Use when you only need prefix sums or range sums (not range min/max) and only point updates (not range updates). Key operations: update(i, delta) adds delta to index i. query(i) returns prefix sum [1..i]. range_query(l, r) = query(r) – query(l-1).

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

    def update(self, i: int, delta: int):
        while i  int:
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)  # remove lowest set bit
        return total

    def range_query(self, l: int, r: int) -> int:
        return self.query(r) - self.query(l - 1)

# Count of Smaller Numbers After Self (LC 315): coordinate compress, BIT
def count_smaller(nums: list[int]) -> list[int]:
    sorted_unique = sorted(set(nums))
    rank = {v: i+1 for i, v in enumerate(sorted_unique)}
    bit = BIT(len(sorted_unique))
    result = []
    for n in reversed(nums):
        result.append(bit.query(rank[n] - 1))  # count smaller elements
        bit.update(rank[n], 1)
    return result[::-1]

Segment Tree – Range Queries and Point Updates

class SegmentTree:
    def __init__(self, nums: list[int]):
        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
        else:
            mid = (start + end) // 2
            if idx  int:
        if end is None: end = self.n - 1
        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(l, r, 2*node+1, start, mid) +
                self.query(l, r, 2*node+2, mid+1, end))
# O(n) build, O(log n) update and query

Lazy Propagation – Range Updates

# Range update (add val to all elements in [l, r]) + range sum query
class LazySegTree:
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (4 * n)
        self.lazy = [0] * (4 * n)

    def _push_down(self, node, start, end):
        if self.lazy[node] != 0:
            mid = (start + end) // 2
            for child in [2*node+1, 2*node+2]:
                size = (mid - start + 1) if child == 2*node+1 else (end - mid)
                self.tree[child] += self.lazy[node] * size
                self.lazy[child] += self.lazy[node]
            self.lazy[node] = 0

    def range_update(self, l, r, val, node=0, start=0, end=None):
        if end is None: end = self.n - 1
        if r < start or end < l: return
        if l <= start and end  int:
        if end is None: end = self.n - 1
        if r < start or end < l: return 0
        if l <= start and end <= r: return self.tree[node]
        self._push_down(node, start, end)
        mid = (start + end) // 2
        return (self.range_query(l, r, 2*node+1, start, mid) +
                self.range_query(l, r, 2*node+2, mid+1, end))

When to Use BIT vs Segment Tree

Use BIT (Fenwick Tree) when: point updates + prefix/range sum queries only. Simpler code, smaller constant factor, O(log n) both ops. Examples: count inversions, count smaller elements (LC 315), range sum query (LC 307). Use Segment Tree when: range min/max queries (not just sum), lazy range updates (add/set a value to a range), more complex aggregations (GCD, OR, AND over range). Segment tree is more general but more code. Use Lazy Segment Tree when: range updates (update all elements in [l,r]) + range queries. Without lazy propagation, range updates are O(n) per update. Lazy defers updates to save work. Interview tip: BIT is usually sufficient for sum problems. Jump to segment tree only if you need range min/max or range updates.

Meta coding interviews include advanced data structure problems with range queries. See typical problems at Meta interview: segment tree and range query problems.

Databricks interviews test range query and aggregation data structures. Review patterns for Databricks interview: range queries and stream aggregation.

Atlassian coding rounds include advanced data structure problems. See common patterns for Atlassian interview: advanced data structure problems.

Scroll to Top