Segment Tree & Fenwick Tree (BIT) Explained: Range Queries, Updates & Lazy Propagation

Segment trees and Fenwick trees sit at the edge of the standard interview syllabus. Many candidates skip them, which is reasonable for most loops, but when a problem needs them, nothing else is fast enough, and an O(n log n) solution with a BIT looks very strong next to an O(n²) brute force. This guide explains both from first principles, with complete code, dry runs, lazy propagation, and an honest section on when interviews actually ask for them.

The Range Query Problem: Why Prefix Sums Are Not Enough

You have an array of n numbers and two kinds of operations, interleaved: update (change a[i]) and query (sum of a[l..r]). This is Range Sum Query - Mutable (LeetCode 307).

The key idea behind both trees: precompute sums over a set of blocks such that any prefix (or range) is a union of O(log n) blocks, and any single element belongs to only O(log n) blocks. Then queries combine few blocks, and updates touch few blocks. The two structures differ in how they choose the blocks.

Fenwick Tree (Binary Indexed Tree): Ten Lines of Code

Use 1-based indexing. Let lowbit(i) = i & -i, the value of the lowest set bit of i (see bit manipulation tricks for why that expression works). Then tree[i] stores the sum of the block (i − lowbit(i), i]: the last lowbit(i) elements ending at i.

• Prefix query(i): add tree[i], then jump to i − lowbit(i), the end of the previous block. Each jump removes one set bit, so at most log₂ n steps.
• Update(i, delta): add delta to tree[i], then jump to i + lowbit(i), the next block that also contains i. Each jump moves the lowest set bit up, so at most log₂ n steps.
• Range sum(l, r) = query(r) − query(l − 1). This subtraction is why a BIT needs an invertible operation.

class Fenwick {
    private final long[] tree;           // 1-indexed

    Fenwick(int n) { tree = new long[n + 1]; }

    void add(int i, long delta) {        // a[i] += delta, i is 1-based
        for (; i < tree.length; i += i & -i) tree[i] += delta;
    }

    long prefix(int i) {                 // sum of a[1..i]
        long s = 0;
        for (; i > 0; i -= i & -i) s += tree[i];
        return s;
    }

    long rangeSum(int l, int r) { return prefix(r) - prefix(l - 1); }
}

struct Fenwick {
    int n;
    vector<long long> t;
    explicit Fenwick(int n) : n(n), t(n + 1, 0) {}
    void add(int i, long long d) { for (; i <= n; i += i & -i) t[i] += d; }
    long long prefix(int i) const {
        long long s = 0;
        for (; i > 0; i -= i & -i) s += t[i];
        return s;
    }
    long long rangeSum(int l, int r) const { return prefix(r) - prefix(l - 1); }
};

class NumArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.nums = nums[:]
        self.tree = [0] * (self.n + 1)
        for i, v in enumerate(nums, 1):          # O(n) build
            self.tree[i] += v
            j = i + (i & -i)
            if j <= self.n:
                self.tree[j] += self.tree[i]     # push this block's sum to its parent

    def _prefix(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def update(self, index, val):
        delta = val - self.nums[index]
        self.nums[index] = val
        i = index + 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def sumRange(self, left, right):
        return self._prefix(right + 1) - self._prefix(left)

Note that LeetCode's update sets a value, while the BIT adds a delta, so you keep the original array to compute the difference. The O(n) build pushes each node's total to its "parent" i + lowbit(i); calling add n times also works in O(n log n).

Fenwick Tree Dry Run

Array (1-indexed): a = [3, 2, −1, 6, 5, 4, −3, 3]. Using the block table above:

1. prefix(7): i = 7 (111): add tree[7] = −3. i = 6 (110): add tree[6] = 9. i = 4 (100): add tree[4] = 10. i = 0: stop. Total 16. Check: 3 + 2 − 1 + 6 + 5 + 4 − 3 = 16. Three steps for three set bits in 7.
2. add(3, +10): i = 3: tree[3] = 9. i = 4: tree[4] = 20. i = 8: tree[8] = 29. i = 16 > 8: stop. Exactly the blocks that contain index 3.
3. rangeSum(3, 5) after the update = prefix(5) − prefix(2) = (tree[5] + tree[4]) − tree[2] = (5 + 20) − 5 = 20. Check: 9 + 6 + 5 = 20.

Range Updates with Fenwick Trees

Range update, point query

Store the difference array in the BIT. To add x to every element in [l, r], do add(l, x) and add(r + 1, −x). The value of a[i] is then prefix(i) (plus the original value). Both operations O(log n).

Range update, range query (two BITs)

To support both "add x to [l, r]" and "sum of [l, r]", maintain two BITs, B1 and B2:

class RangeFenwick:
    def __init__(self, n):
        self.n = n
        self.b1 = [0] * (n + 2)
        self.b2 = [0] * (n + 2)

    def _add(self, t, i, v):
        while i <= self.n:
            t[i] += v
            i += i & -i

    def _sum(self, t, i):
        s = 0
        while i > 0:
            s += t[i]
            i -= i & -i
        return s

    def range_add(self, l, r, x):            # 1-based, inclusive
        self._add(self.b1, l, x)
        self._add(self.b1, r + 1, -x)
        self._add(self.b2, l, x * (l - 1))
        self._add(self.b2, r + 1, -x * r)

    def prefix(self, i):
        return self._sum(self.b1, i) * i - self._sum(self.b2, i)

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

Why it works: after adding x on [l, r], the true prefix sum at i is 0 for i < l, x·(i − l + 1) for l ≤ i ≤ r, and x·(r − l + 1) for i > r. B1 contributes x·i in the middle region and B2 subtracts the constant x·(l − 1); beyond r, the two corrections cancel to the constant. You do not need to derive this in an interview, but knowing that a BIT can do it is useful.

2D BIT: nest the loops (for i ...: for j ...) to get O(log n · log m) updates and rectangle-prefix queries, which solves Range Sum Query 2D - Mutable (308).

Segment Tree: Structure, Build, Query, Update

A segment tree is a binary tree in which every node represents a contiguous range of the array and stores the merge (sum, min, max...) of that range. The root covers [0, n−1]; a node covering [l, r] has children covering [l, mid] and [mid+1, r]; leaves cover single elements. Stored heap-style: node 1 is the root, node k's children are 2k and 2k+1.

Query [l, r]: starting from the root, if the node's range is entirely inside [l, r], return its value; if entirely outside, return the identity (0 for sum, +∞ for min); otherwise recurse into both children and merge. At most four nodes are visited per level (at most two partially overlapping), so O(log n).

Point update: walk to the leaf, change it, and recompute every ancestor on the way back. O(log n).

class SegmentTree {
    private final int n;
    private final long[] tree;

    SegmentTree(int[] a) {
        n = a.length;
        tree = new long[4 * n];
        build(1, 0, n - 1, a);
    }

    private void build(int node, int l, int r, int[] a) {
        if (l == r) { tree[node] = a[l]; return; }
        int mid = (l + r) >>> 1;
        build(2 * node, l, mid, a);
        build(2 * node + 1, mid + 1, r, a);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void update(int idx, int val) { update(1, 0, n - 1, idx, val); }

    private void update(int node, int l, int r, int idx, int val) {
        if (l == r) { tree[node] = val; return; }
        int mid = (l + r) >>> 1;
        if (idx <= mid) update(2 * node, l, mid, idx, val);
        else update(2 * node + 1, mid + 1, r, idx, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    long query(int ql, int qr) { return query(1, 0, n - 1, ql, qr); }

    private long query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;                 // no overlap: identity
        if (ql <= l && r <= qr) return tree[node];      // full overlap
        int mid = (l + r) >>> 1;                         // partial overlap
        return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr);
    }
}

class MinSegTree:
    def __init__(self, a):
        self.n = len(a)
        self.t = [float("inf")] * (4 * self.n)
        self._build(1, 0, self.n - 1, a)

    def _build(self, node, l, r, a):
        if l == r:
            self.t[node] = a[l]
            return
        m = (l + r) // 2
        self._build(2 * node, l, m, a)
        self._build(2 * node + 1, m + 1, r, a)
        self.t[node] = min(self.t[2 * node], self.t[2 * node + 1])

    def update(self, i, val, node=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        if l == r:
            self.t[node] = val
            return
        m = (l + r) // 2
        if i <= m:
            self.update(i, val, 2 * node, l, m)
        else:
            self.update(i, val, 2 * node + 1, m + 1, r)
        self.t[node] = min(self.t[2 * node], self.t[2 * node + 1])

    def query(self, ql, qr, node=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        if qr < l or r < ql:
            return float("inf")
        if ql <= l and r <= qr:
            return self.t[node]
        m = (l + r) // 2
        return min(self.query(ql, qr, 2 * node, l, m),
                   self.query(ql, qr, 2 * node + 1, m + 1, r))

Dry run of sum query [1, 3] on the tree above (answer 1 + 5 + 3 = 9): root [0..4] partially overlaps → recurse. [0..2] partial → [0..1] partial → [0] outside (0), [1] inside (1); [2] inside (5): subtotal 6. [3..4] partial → [3] inside (3), [4] outside (0): subtotal 3. Total 9, visiting 9 nodes. On large arrays, the number of visited nodes stays around 4 log n.

Iterative (Bottom-Up) Segment Tree in 2n Space

For point updates and range queries, a non-recursive version is shorter and faster. Leaves live at indices n..2n−1; node i's children are 2i and 2i+1.

struct IterSegTree {
    int n;
    vector<long long> t;
    explicit IterSegTree(const vector<long long>& a) : n(a.size()), t(2 * a.size()) {
        for (int i = 0; i < n; i++) t[n + i] = a[i];
        for (int i = n - 1; i >= 1; i--) t[i] = t[2 * i] + t[2 * i + 1];
    }
    void update(int p, long long val) {          // set a[p] = val
        for (t[p += n] = val; p > 1; p >>= 1) t[p >> 1] = t[p] + t[p ^ 1];
    }
    long long query(int l, int r) {              // sum on [l, r), half-open
        long long res = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += t[l++];
            if (r & 1) res += t[--r];
        }
        return res;
    }
};

This works for any n, not just powers of two, for commutative merges like sum, min and max. (For non-commutative merges, keep separate left and right accumulators.) It is a favourite in competitive programming; in an interview, the recursive version is easier to explain and extend.

Lazy Propagation: Range Updates in O(log n)

Now updates are ranges: "add v to every element in [l, r]". Updating each leaf is O(n). The fix: when an update fully covers a node, update the node's stored sum directly (sum += v × length) and record a lazy tag meaning "my children still owe +v". Before any later operation descends into that node, push the tag down to the children.

struct LazySegTree {
    int n;
    vector<long long> sum, lazy;

    explicit LazySegTree(const vector<long long>& a)
        : n(a.size()), sum(4 * a.size()), lazy(4 * a.size()) {
        build(1, 0, n - 1, a);
    }

    void build(int node, int l, int r, const vector<long long>& a) {
        if (l == r) { sum[node] = a[l]; return; }
        int m = (l + r) / 2;
        build(2 * node, l, m, a);
        build(2 * node + 1, m + 1, r, a);
        sum[node] = sum[2 * node] + sum[2 * node + 1];
    }

    void apply(int node, int l, int r, long long v) {
        sum[node] += v * (r - l + 1);    // whole range shifts by v
        lazy[node] += v;                 // children still owe v
    }

    void push(int node, int l, int r) {
        if (lazy[node] != 0) {
            int m = (l + r) / 2;
            apply(2 * node, l, m, lazy[node]);
            apply(2 * node + 1, m + 1, r, lazy[node]);
            lazy[node] = 0;
        }
    }

    void update(int ql, int qr, long long v) { update(1, 0, n - 1, ql, qr, v); }
    void update(int node, int l, int r, int ql, int qr, long long v) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { apply(node, l, r, v); return; }
        push(node, l, r);
        int m = (l + r) / 2;
        update(2 * node, l, m, ql, qr, v);
        update(2 * node + 1, m + 1, r, ql, qr, v);
        sum[node] = sum[2 * node] + sum[2 * node + 1];
    }

    long long query(int ql, int qr) { return query(1, 0, n - 1, ql, qr); }
    long long query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return sum[node];
        push(node, l, r);
        int m = (l + r) / 2;
        return query(2 * node, l, m, ql, qr) + query(2 * node + 1, m + 1, r, ql, qr);
    }
};

Walkthrough on a = [2, 1, 5, 3, 4]: update(0, 2, +10) reaches node [0..2], which is fully covered. Its sum becomes 8 + 3 × 10 = 38 and its lazy tag becomes 10; its children [0..1] and [2] are untouched. The root is recomputed as 38 + 7 = 45. Now query(1, 1) descends into [0..2], so push runs: [0..1] gets sum 3 + 20 = 23, lazy 10; [2] gets 15, lazy 10. Descending into [0..1] pushes again: [0] becomes 12, [1] becomes 11. Answer 11 = 1 + 10. Correct, and only the nodes on the query path were ever touched.

The rules to remember: push before descending, recompute after returning, and make sure the tag type composes (two pending "add" tags add up; "assign" tags overwrite; mixing assign and add requires ordering rules).

Custom Merge Functions: What Else a Segment Tree Can Store

The segment tree's power is that the node value can be anything with an associative merge. Some useful ones:

The maximum-subarray node is a great interview discussion: for children L and R, best = max(L.best, R.best, L.suffix + R.prefix), prefix = max(L.prefix, L.sum + R.prefix), suffix = max(R.suffix, R.sum + L.suffix), sum = L.sum + R.sum. It is Kadane's algorithm (see Kadane's algorithm explained) turned into a mergeable structure.

Another trick: descending the tree to find the first index where a prefix sum exceeds k, in O(log n) rather than O(log² n) with binary search on top of queries. BITs support the same descent using powers of two.

Fenwick Tree vs Segment Tree: Which to Use

Decision rule: if the operation is a sum or count, use a BIT; otherwise use a segment tree. If there are no updates at all, use prefix sums (sums) or a sparse table (min/max/gcd).

Interview Problems That Use BITs and Segment Trees

Count of Smaller Numbers After Self (315)

For each element, count smaller elements to its right. Traverse from right to left with a BIT over value ranks: for each value, query how many ranks below it have been seen, then add 1 at its rank. Values can be negative or large, so first coordinate-compress: sort the distinct values and map each to its index.

def count_smaller(nums):
    ranks = {v: i + 1 for i, v in enumerate(sorted(set(nums)))}   # 1-based ranks
    m = len(ranks)
    tree = [0] * (m + 1)

    def add(i):
        while i <= m:
            tree[i] += 1
            i += i & -i

    def prefix(i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    res = [0] * len(nums)
    for i in range(len(nums) - 1, -1, -1):
        r = ranks[nums[i]]
        res[i] = prefix(r - 1)       # strictly smaller values seen to the right
        add(r)
    return res

Dry run for [5, 2, 6, 1]: ranks 1→1, 2→2, 5→3, 6→4. i=3 (1): prefix(0)=0, add rank 1. i=2 (6): prefix(3)=1, add 4. i=1 (2): prefix(1)=1, add 2. i=0 (5): prefix(2)=2, add 3. Result [2, 1, 1, 0]. O(n log n). The merge-sort alternative also runs in O(n log n); offering both is ideal.

More problems in the same family

• Reverse Pairs (493): count i < j with nums[i] > 2·nums[j]. BIT over compressed values including 2·x, or modified merge sort.
• Count of Range Sum (327): count subarrays with sum in [lower, upper]; BIT over compressed prefix sums, querying the window [P − upper, P − lower].
• Global inversions / count inversions: classic BIT or merge sort; a staple of campus placement tests.
• Range Sum Query 2D - Mutable (308): 2D BIT.
• Falling Squares (699) and My Calendar III (732): range assign/add with max query; lazy segment tree over compressed coordinates (or a simpler sweep since n is small).
• Range Module (715): dynamic segment tree or an ordered map of intervals; the map version is usually expected. See intervals interview problems.
• Longest Increasing Subsequence variants: a max-BIT over values gives O(n log n) for "LIS with weights" or "number of LIS" style problems.

When Do Interviews Actually Ask Segment Trees?

An honest calibration, based on commonly reported interview experiences rather than hard data: at most Indian product companies and in most Amazon and Microsoft loops, segment trees are uncommon. They appear more often at Google, in online assessments for companies whose tests lean towards competitive programming (and on platforms that use those question banks), and for roles at trading firms. Processes change and vary by team, so check recent experiences for your target company and ask your recruiter.

Interviewers usually also accept simpler alternatives when they exist: merge sort for inversions, an ordered set (TreeMap, std::set, SortedList) for many "count smaller" variants, and binary search on the answer in some range problems. Mentioning the segment tree as the general solution and then choosing the simplest structure that works is the strongest answer. When you discuss complexity, be precise about log factors; the Big-O guide covers how to present O(n log n) vs O(n log² n).

Common Segment Tree and BIT Mistakes

• Index base confusion. BITs are 1-indexed; index 0 makes the update loop spin forever because 0 & -0 = 0. Convert with i + 1.
• Allocating 2n for a recursive segment tree. Use 4n; 2n only works for the iterative layout.
• Wrong identity element for out-of-range nodes: 0 for sum, +∞ for min, −∞ for max, 0 for gcd.
• Forgetting to push lazy tags before descending, or forgetting to recompute the parent after an update.
• Setting vs adding in BIT updates (LeetCode 307's update sets a value; the BIT needs the delta).
• Overflow in sums: use long / long long, especially with lazy v × length.
• No coordinate compression when values go up to 10⁹ or are negative.
• Using a BIT for range min with arbitrary updates.

Practice List: From First BIT to Lazy Segment Tree

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.