When should you use a Fenwick Tree vs a Segment Tree?

Use a Fenwick Tree (BIT) when you only need point updates and prefix sum/XOR queries — it is simpler to code and has a lower constant factor. Use a Segment Tree when you need range queries (min, max, GCD) or range updates. If you need lazy propagation (efficient bulk range updates), a Segment Tree with lazy propagation is the standard solution.

How does a Fenwick Tree achieve O(log n) updates and queries?

Each index i in the BIT is responsible for a range of elements determined by its lowest set bit (i & -i). Update: add delta to tree[i], then jump to tree[i + (i & -i)] and repeat until out of bounds. Query (prefix sum 1..i): sum tree[i], then jump to tree[i - (i & -i)] and repeat until i = 0. Each operation visits O(log n) nodes because each step flips the lowest set bit.

What is lazy propagation in a Segment Tree and when is it needed?

Lazy propagation defers range updates. Instead of updating all O(n) elements in a range, store a pending (lazy) tag at the covering node. When you later query or update a node with a pending tag, push the tag down to its children before proceeding. This makes range updates O(log n) instead of O(n). Needed for problems like "add 5 to all elements in [l, r]" or "set all elements in [l, r] to x".

How do you count elements smaller than x to the right of each position (LC 315)?

Process the array right to left. Coordinate-compress the values to [1..n]. For each element at position i: query the BIT for the prefix sum [1..value-1] (count of values already inserted that are smaller). Update the BIT at position value by 1 (record that this value has been seen). The query result is the count of smaller elements to the right of position i. O(n log n) total.

How much space does a Segment Tree require?

A Segment Tree for an array of n elements requires O(4n) space in the standard array-based implementation (allocate tree[4*n]). This is because the tree is a complete binary tree of height ceil(log2(n)) + 1; the worst case for the array storage is 4n. In practice, 2 * (next power of 2 >= n) is the tighter bound, but 4n is safe for competitive programming.

Segment Tree and Fenwick Tree (BIT) Interview Patterns: Range Queries and Updates (2025)

⏱ 5 min read

When to Use Advanced Range Data Structures

A plain array supports point updates in O(1) and range queries (sum, min, max) in O(n). A prefix sum array supports range sum queries in O(1) but requires O(n) to rebuild after an update. When you need both efficient updates and efficient range queries, use a Segment Tree or Fenwick Tree (Binary Indexed Tree / BIT). Segment Tree: supports range queries and range updates in O(log n). More flexible — works for sum, min, max, GCD, XOR, and custom operations. Fenwick Tree: supports point updates and prefix queries in O(log n). Simpler to code, lower constant factor, but less flexible (sum/XOR only, not min/max). Rule of thumb: if you need min/max range queries or range updates: use a Segment Tree. If you only need point updates and prefix sum queries: use a Fenwick Tree.

Fenwick Tree (BIT) Implementation

A Fenwick Tree stores partial sums in a clever array structure. Each index i is responsible for a range of elements determined by the lowest set bit of i (i & -i). Point update and prefix sum query are both O(log n).

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

    def update(self, i, delta):  # 1-indexed
        while i  0:
            s += self.tree[i]
            i -= i & (-i)  # move to responsible parent
        return s

    def range_query(self, l, r):  # sum [l..r]
        return self.query(r) - self.query(l - 1)

Use cases: LC 307 (Range Sum Query – Mutable): point update + range sum query. LC 315 (Count of Smaller Numbers After Self): for each element, query how many smaller elements have been inserted to the right. Process right to left; use BIT indexed by value. LC 493 (Reverse Pairs): similar pattern — count inversions using BIT on compressed values.

Segment Tree Implementation

A Segment Tree is a binary tree where each node covers a range [l, r]. Leaf nodes cover individual elements. Internal nodes store the aggregate (sum, min, max) of their range. Build in O(n); query and point update in O(log n). Range update with lazy propagation: O(log n) per range update.

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)
        self._build(nums, 1, 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, start, mid)
            self._build(nums, 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]

    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, start, mid, l, r) +
                self.query(2*node+1, mid+1, end, l, r))

Lazy Propagation for Range Updates

Lazy propagation defers range updates: instead of updating all O(n) elements in a range immediately, store a pending update (lazy tag) at the covering node and apply it when the node is visited. This enables O(log n) range updates. Pattern: maintain a lazy array alongside the tree. On range update [l, r, val]: update nodes covering [l, r] and set lazy[node] = val. On query or further update: push the lazy tag down to children before recursing. LC 218 (The Skyline Problem), LC 2407 (Longest Increasing Subsequence using BIT for optimization).

Order Statistics and Merge Sort Tree

Order statistics: find the k-th smallest element in a range, or count elements ≤ x in a range. Approach: Segment Tree with each node storing a sorted list of elements in its range (Merge Sort Tree). Build: O(n log n) space and time. Query (count elements ≤ x in [l, r]): O(log^2 n) using binary search at each node. Alternatively, use a Segment Tree on coordinate-compressed values: compress all values to [1..M], then for each position query/update by value. This pattern solves LC 315 (Count of Smaller Numbers After Self) and similar offline range query problems. Persistent Segment Tree: each update creates a new root, preserving history. Supports “k-th smallest in range [l, r]” queries in O(log n) using the difference between two versions.