Fenwick & Segment Tree

At a glance

The instinct

A prefix-sum array answers "sum of l..r" in O(1), but one update forces O(n) rebuild. A plain array updates in O(1) but sums in O(n). When a problem interleaves updates and range queries, you need something in between: a tree of precomputed partial answers where any range is stitched from O(log n) pieces and any update touches O(log n) pieces.

• Fenwick tree (Binary Indexed Tree): a single array where tree[i] covers the lowbit(i) elements ending at i. Tiny code, ideal for prefix sums and counts.
• Segment tree: a binary tree where each node stores the answer for a half-split interval. More code, but handles min, max, gcd, and range updates with lazy propagation.

Recognise it

Not this pattern if...

• The array never changes: a static prefix-sum array (or sparse table for min) is simpler.
• Queries come only after all updates: apply all updates with a difference array, then prefix sum.
• You only need the global max/min of a changing set: a heap or TreeMap is enough.
• Only "sliding window" ranges are asked: a monotonic deque or sliding window does it in O(n).

Memory hack

Analogy: a company's reporting chain. Each manager knows the total sales of their team. To learn sales for any stretch of employees you ask a few managers, not every employee. When one employee's number changes, only the managers above them update their totals.

Say it out loud in the interview:

1. "Updates and range queries are interleaved, so prefix sums alone are too slow."
2. "The operation is a sum/count (Fenwick) or min/max/needs range updates (segment tree)."
3. "If values are large or negative, I'll coordinate-compress them to ranks first."

How it works

Fenwick (1-indexed). lowbit(i) = i & -i is the lowest set bit. tree[i] stores the sum of (i - lowbit(i), i]. A prefix query for i repeatedly adds tree[i] and strips the lowest bit; an update starts at i and adds the lowest bit to reach every node whose block covers i. Range sum l..r is prefix(r) - prefix(l-1).

Query trace for prefix(13):

Three blocks, one per set bit of 13.

Counting trick (Count of Smaller Numbers After Self). Compress values to ranks 1..m. Sweep from right to left: answer for x is prefix(rank(x) - 1), then update(rank(x), +1). The Fenwick tree is acting as a live histogram.

Segment tree. Node node covers [lo, hi]; children cover the two halves. A query descends only into children that overlap [l, r], and at most about four nodes per level are touched, giving O(log n). Use it when the combine function is min/max/gcd, or add lazy propagation for range assignments.

Java template

import java.util.*;

class Fenwick {                                   // point update, prefix/range sum, 1-indexed
    private final long[] tree;
    Fenwick(int n) { tree = new long[n + 1]; }

    void add(int i, long delta) {                 // a[i] += delta
        for (; i < tree.length; i += i & -i) tree[i] += delta;
    }
    long prefix(int i) {                          // a[1] + ... + a[i]
        long s = 0;
        for (; i > 0; i -= i & -i) s += tree[i];
        return s;
    }
    long range(int l, int r) { return prefix(r) - prefix(l - 1); }

    static int[] ranks(int[] nums) {              // coordinate compression to 1..m
        int[] sorted = Arrays.stream(nums).distinct().sorted().toArray();
        int[] r = new int[nums.length];
        for (int i = 0; i < nums.length; i++) r[i] = Arrays.binarySearch(sorted, nums[i]) + 1;
        return r;
    }
}

class SegmentTree {                               // point assign, range combine (here: min)
    private final int n;
    private final int[] t;
    private static final int IDENTITY = Integer.MAX_VALUE;   // identity for min; 0 for sum

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

    private int combine(int x, int y) { return Math.min(x, y); }   // problem-specific

    private void build(int node, int lo, int hi, int[] a) {
        if (lo == hi) { t[node] = a[lo]; return; }
        int mid = (lo + hi) >>> 1;
        build(2 * node, lo, mid, a);
        build(2 * node + 1, mid + 1, hi, a);
        t[node] = combine(t[2 * node], t[2 * node + 1]);
    }
    void set(int idx, int val) { set(1, 0, n - 1, idx, val); }
    private void set(int node, int lo, int hi, int idx, int val) {
        if (lo == hi) { t[node] = val; return; }
        int mid = (lo + hi) >>> 1;
        if (idx <= mid) set(2 * node, lo, mid, idx, val); else set(2 * node + 1, mid + 1, hi, idx, val);
        t[node] = combine(t[2 * node], t[2 * node + 1]);
    }
    int query(int l, int r) { return query(1, 0, n - 1, l, r); }
    private int query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return IDENTITY;            // fully out: ignore
        if (l <= lo && hi <= r) return t[node];           // fully in: return
        int mid = (lo + hi) >>> 1;                        // partly in: split
        return combine(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r));
    }
}

For Range Sum Query - Mutable with Fenwick, update(i, val) becomes add(i + 1, val - a[i]) and you keep a copy of a to know the old value.

Complexity

Coordinate compression adds an O(n log n) sort.

Variations

• Point update, range sum: the textbook case. Example: Range Sum Query - Mutable.
• Value-indexed counting: Fenwick over ranks as a dynamic histogram. Example: Count of Smaller Numbers After Self (merge sort also works).
• Range update, point query: Fenwick over a difference array; add(l, v), add(r+1, -v), value = prefix(i).
• Range min/max: segment tree with min/max combine; Fenwick cannot subtract to isolate a range.
• Lazy propagation: postpone range additions/assignments at internal nodes until a query needs them.
• 2D Fenwick: nested loops over both indices for submatrix sums with updates.

Common mistakes

• Using Fenwick for range min: prefix(r) - prefix(l-1) only works for invertible operations like sum or xor.
• Sizing a recursive segment tree array as 2n; the safe bound is 4n.
• Forgetting to update the stored copy of the array, so the next delta val - a[i] is wrong.
• Skipping coordinate compression when values reach 10^9 or are negative, causing huge arrays or negative indices.
• Returning 0 as the out-of-range identity in a min tree; it must be the operation's neutral value.

All practice problems

2 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.