Segment & Fenwick Trees

Range queries on changing data: why prefix sums break, how segment trees answer any range in O(log n), and the Fenwick tree's beautiful bit trick.

Why We Need Segment & Fenwick Trees

Imagine you have a large array of numbers and need to perform two operations millions of times:

Update a single element at index i.
Range Query: Calculate the sum (or minimum/maximum) of elements from index L to R.

If we use a plain array, updates are fast ($O(1)$) but query takes $O(n)$ to sum the range. If we use a Prefix Sum array, queries are fast ($O(1)$) but updating an element requires recomputing prefix sums, which takes $O(n)$ time.

To solve this trade-off and make both operations run in $O(\log n)$ time, we need a Segment Tree or a Fenwick Tree (Binary Indexed Tree).

💡 Visualizing the structures:

Think of a Segment Tree like a Tournament Bracket. To find the overall champion among 8 teams, you don't re-run all matches. You look at the final match (which combines the semi-finals, which combine the quarter-finals). If one team changes their score, you only need to re-evaluate the matches along their path to the top, not the entire tournament.

Think of a Fenwick Tree like a smart budgeting system where you keep envelopes for specific intervals defined by binary numbers (e.g., an envelope for Day 1, Days 1–2, Day 3, Days 1–4). To find your total spending up to Day 7, you don't add 7 separate days; you just add the envelopes for Days 1–4, Days 5–6, and Day 7.

When to Use

Dynamic range sum / min / max queries with frequent point updates.
- LeetCode Link: LeetCode 307: Range Sum Query - Mutable
Counting inversions in an array.

The problem both trees solve

Prefix sums answer "sum of elements i…j" in O(1) — as long as the array never changes. One update breaks them: change a[3] and every prefix from index 3 onward is stale — O(n) to rebuild. So you're stuck choosing:

	Query range	Update element
Plain array	O(n) — walk the range	O(1)
Prefix sums	O(1)	O(n) — rebuild
Segment / Fenwick tree	O(log n)	O(log n)

When both operations are frequent — live leaderboards, counting inversions, range-minimum over a changing series — the logarithmic middle ground wins. That's the entire reason these structures exist: range queries interleaved with point updates.

Segment tree — divide the array like a tournament

A segment tree is a binary tree where each node owns an interval of the array and stores an aggregate (sum, min, max — anything combinable) of that interval. The root owns everything; children split the parent's interval in half; leaves own single elements:

array: [2, 5, 1, 4, 9, 3]                 node = sum of its interval

                 [0..5]=24
               /          \
        [0..2]=8          [3..5]=16
        /     \           /      \
    [0..1]=7  [2]=1   [3..4]=13  [5]=3
    /    \            /     \
  [0]=2 [1]=5      [3]=4  [4]=9

Query "sum of 1…4": walk down, and at each node take one of three exits — interval fully inside the query (use its stored value, stop), fully outside (contribute 0, stop), or partial (recurse both children). Here: [1]=5 + [2]=1 + [3..4]=13 = 19. Because the query range "fragments" into at most ~2 nodes per level, the walk touches O(log n) nodes.

Update a[4] = 6: change the leaf, then recompute the aggregates on the single root-to-leaf path above it — also O(log n) (here: [4], [3..4], [3..5], root).

The implementation everyone actually writes stores the tree in a flat array (the heap trick: children of i at 2i and 2i+1):

Python

class SegmentTree:
    def __init__(self, a):
        self.n = len(a)
        self.t = [0] * (2 * self.n)
        self.t[self.n:] = a                      # leaves sit at n..2n-1
        for i in range(self.n - 1, 0, -1):       # build parents bottom-up
            self.t[i] = self.t[2*i] + self.t[2*i + 1]

    def update(self, i, value):                  # point update: O(log n)
        i += self.n                              # jump to the leaf
        self.t[i] = value
        while i > 1:
            i //= 2                              # climb to the root
            self.t[i] = self.t[2*i] + self.t[2*i + 1]

    def query(self, lo, hi):                     # sum of [lo, hi): O(log n)
        s, lo, hi = 0, lo + self.n, hi + self.n
        while lo < hi:
            if lo & 1: s += self.t[lo]; lo += 1  # lo is a right child: take it
            if hi & 1: hi -= 1; s += self.t[hi]  # hi is a right edge: take it
            lo //= 2; hi //= 2                   # climb one level
        return s

Java

// Java
public class SegmentTree {
    private int n;
    private int[] t;

    public SegmentTree(int[] a) {
        this.n = a.length;
        this.t = new int[2 * n];
        // leaves sit at n..2n-1
        for (int i = 0; i < n; i++) {
            t[n + i] = a[i];
        }
        // build parents bottom-up
        for (int i = n - 1; i > 0; i--) {
            t[i] = t[2 * i] + t[2 * i + 1];
        }
    }

    public void update(int i, int value) { // point update: O(log n)
        i += n; // jump to the leaf
        t[i] = value;
        while (i > 1) {
            i /= 2; // climb to the root
            t[i] = t[2 * i] + t[2 * i + 1];
        }
    }

    public int query(int lo, int hi) { // sum of [lo, hi): O(log n)
        int s = 0;
        lo += n;
        hi += n;
        while (lo < hi) {
            if ((lo & 1) == 1) {
                s += t[lo];
                lo++;
            }
            if ((hi & 1) == 1) {
                hi--;
                s += t[hi];
            }
            lo /= 2;
            hi /= 2;
        }
        return s;
    }
}

C++

// C++
#include <vector>

class SegmentTree {
private:
    int n;
    std::vector<int> t;

public:
    SegmentTree(const std::vector<int>& a) {
        n = a.size();
        t.assign(2 * n, 0);
        // leaves sit at n..2n-1
        for (int i = 0; i < n; i++) {
            t[n + i] = a[i];
        }
        // build parents bottom-up
        for (int i = n - 1; i > 0; i--) {
            t[i] = t[2 * i] + t[2 * i + 1];
        }
    }

    void update(int i, int value) { // point update: O(log n)
        i += n; // jump to the leaf
        t[i] = value;
        while (i > 1) {
            i /= 2; // climb to the root
            t[i] = t[2 * i] + t[2 * i + 1];
        }
    }

    int query(int lo, int hi) { // sum of [lo, hi): O(log n)
        int s = 0;
        lo += n;
        hi += n;
        while (lo < hi) {
            if (lo & 1) {
                s += t[lo];
                lo++;
            }
            if (hi & 1) {
                hi--;
                s += t[hi];
            }
            lo /= 2;
            hi /= 2;
        }
        return s;
    }
};

Swap + for min/max/gcd and the same skeleton answers range-minimum, range-max — the only requirement on the operation is associativity (grouping doesn't matter), because the tree combines partial answers in chunks.

One name to know, not implement, at interview level: lazy propagation — the extension for range updates ("add 5 to elements 2…900"): store pending updates at high nodes and push them down only when a query actually descends, keeping range-update and range-query at O(log n).

Fenwick tree (BIT) — the same power, 10 lines

The Fenwick tree (Binary Indexed Tree) handles the most common case — prefix sums with point updates — in a fraction of the code, using a trick on the binary representation of indices. Each position i is responsible for a block of lowbit(i) = i & (-i) elements (the value of i's lowest set bit):

index (1-based):  1    2    3    4    5    6    7    8
covers:          [1] [1-2] [3] [1-4] [5] [5-6] [7] [1-8]
lowbit:           1    2    1    4    1    2    1    8

A prefix sum strips lowest bits to jump between blocks; an update adds lowest bits to touch every block containing i:

Python

class Fenwick:
    def __init__(self, n):
        self.t = [0] * (n + 1)               # 1-based!

    def update(self, i, delta):              # a[i] += delta, O(log n)
        while i < len(self.t):
            self.t[i] += delta
            i += i & (-i)                    # next block that contains i

    def prefix(self, i):                     # sum of a[1..i], O(log n)
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)                    # previous block
        return s

    def query(self, lo, hi):                 # sum of [lo, hi]
        return self.prefix(hi) - self.prefix(lo - 1)

Java

// Java
public class Fenwick {
    private int[] t;

    public Fenwick(int n) {
        this.t = new int[n + 1]; // 1-based!
    }

    public void update(int i, int delta) { // a[i] += delta, O(log n)
        while (i < t.length) {
            t[i] += delta;
            i += i & (-i); // next block containing i
        }
    }

    public int prefix(int i) { // sum of a[1..i], O(log n)
        int s = 0;
        while (i > 0) {
            s += t[i];
            i -= i & (-i); // previous block
        }
        return s;
    }

    public int query(int lo, int hi) { // sum of [lo, hi], closed interval
        return prefix(hi) - prefix(lo - 1);
    }
}

C++

// C++
#include <vector>

class Fenwick {
private:
    std::vector<int> t;

public:
    Fenwick(int n) {
        t.assign(n + 1, 0); // 1-based!
    }

    void update(int i, int delta) { // a[i] += delta, O(log n)
        while (i < t.size()) {
            t[i] += delta;
            i += i & (-i); // next block containing i
        }
    }

    int prefix(int i) { // sum of a[1..i], O(log n)
        int s = 0;
        while (i > 0) {
            s += t[i];
            i -= i & (-i); // previous block
        }
        return s;
    }

    int query(int lo, int hi) { // sum of [lo, hi], closed interval
        return prefix(hi) - prefix(lo - 1);
    }
};

Choosing between them, honestly: Fenwick when the operation is sums/counts (invertible — you can subtract prefixes) — shorter, faster constants, harder to get wrong under pressure. Segment tree when you need min/max (not invertible: knowing min(1..8) and min(1..4) doesn't give min(5..8)), range updates, or anything exotic stored per node.

Watch the Fenwick tree run

Each tree slot quietly owns a block of the array. Watch every value ripple into just the few blocks that contain it (the lowest-set-bit hops), then watch a prefix query collect its answer from a handful of blocks instead of re-adding everything.

Fenwick tree — updatable prefix sumstime O(log n) per opspace O(n)

012345678a

tree

1/11Prefix sums answer range questions in O(1) — but one value change forces rebuilding the whole row. The Fenwick tree is the compromise: each slot stores the total of a *block* of values, and both update and query touch only O(log n) slots.

values (≤ 8)query a[1..k]

Where they show up

Interview classics: count inversions / "count of smaller elements to the right" (Fenwick over values: walk right-to-left, query how many smaller values already seen — turning an O(n²) count into O(n log n)); range-sum-with-updates (LeetCode 307, literally this page); sliding-window extremes when the window math gets exotic.
Competitive programming: these are bread and butter — if that's your route, fluency is assumed.
Production: order-book analytics ("volume between price levels x and y, updating per trade" — StockVision's domain), live leaderboards ("how many players score below X?"), monitoring percentiles over rolling counters. Databases solve their version of the same problem with B-tree aggregates.
Calibration: in product-company interviews these are senior/optional — asked occasionally, never as the opener. Master the core structures first; this page is the cherry, not the cake.

Common mistakes

Reaching for a segment tree when prefix sums suffice — no updates? Precompute prefixes, O(1) queries, 3 lines. The fancy structure must earn its complexity.
Off-by-one soup — half-open [lo, hi) vs closed [lo, hi], 0-based array vs 1-based Fenwick. Pick conventions out loud, write them in a comment, test with a 3-element array.
Forgetting Fenwick is 1-based — index 0 has lowbit(0) = 0 and loops forever. The +1 shift is load-bearing.
Using Fenwick for min/max — prefix-min can't be subtracted into range-min; that's segment-tree territory.
Rebuilding per query in disguise — recomputing the tree because "the array changed a lot": batch updates are still O(log n) each; full rebuild is O(n) — know which regime you're in.

Think it through

The classic interview use isn't "range sum" — it's a counting problem in disguise, solved by indexing a Fenwick tree by value instead of position. Reason through the canonical one before revealing.

Think it through: Count of Smaller Numbers After SelfHard — LeetCode 3150/5 stages

PROBLEMFor each element, count how many elements to its RIGHT are strictly smaller. nums = [5,2,6,1] → [2,1,1,0].

1
Restate & brute force
“Obvious solution and its cost?”
2
The reframe
“Process the array right-to-left. At each element, what am I really asking the structure?”
unlocks after the stage above
3
Make values usable as indices
“Values can be huge or negative — how do I index a Fenwick by them?”
unlocks after the stage above
4
Code the template
“Right-to-left: query smaller-count, then insert. Why that order?”
unlocks after the stage above
5
Cost & transfer
“Cost, and where else does this exact pattern appear?”
unlocks after the stage above

Java

// Java — Count of Smaller Numbers After Self
import java.util.*;

public List<Integer> countSmaller(int[] nums) {
    if (nums == null || nums.length == 0) return new ArrayList<>();
    
    // Coordinate compression
    int[] sortedUnique = nums.clone();
    Arrays.sort(sortedUnique);
    Map<Integer, Integer> ranks = new HashMap<>();
    int rank = 1;
    for (int num : sortedUnique) {
        if (!ranks.containsKey(num)) {
            ranks.put(num, rank++);
        }
    }

    int[] tree = new int[ranks.size() + 1];
    
    class FenwickHelper {
        void update(int idx) {
            while (idx < tree.length) {
                tree[idx] += 1;
                idx += idx & -idx;
            }
        }
        int prefix(int idx) {
            int sum = 0;
            while (idx > 0) {
                sum += tree[idx];
                idx -= idx & -idx;
            }
            return sum;
        }
    }
    FenwickHelper f = new FenwickHelper();
    
    Integer[] res = new Integer[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
        int r = ranks.get(nums[i]);
        res[i] = f.prefix(r - 1);
        f.update(r);
    }
    return Arrays.asList(res);
}

C++

// C++ — Count of Smaller Numbers After Self
#include <vector>
#include <algorithm>
#include <unordered_map>

std::vector<int> countSmaller(const std::vector<int>& nums) {
    if (nums.empty()) return {};
    
    // Coordinate compression
    std::vector<int> sorted = nums;
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
    
    std::unordered_map<int, int> ranks;
    for (int i = 0; i < sorted.size(); i++) {
        ranks[sorted[i]] = i + 1; // 1-based ranks
    }
    
    std::vector<int> tree(ranks.size() + 1, 0);
    auto update = [&](int idx) {
        while (idx < tree.size()) {
            tree[idx] += 1;
            idx += idx & -idx;
        }
    };
    auto prefix = [&](int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= idx & -idx;
        }
        return sum;
    };
    
    std::vector<int> res(nums.size());
    for (int i = nums.size() - 1; i >= 0; i--) {
        int r = ranks[nums[i]];
        res[i] = prefix(r - 1);
        update(r);
    }
    return res;
}

Interview perspective

Check yourself

Check yourself0/3 answered

1. What is the primary trade-off that makes Segment and Fenwick Trees necessary over simple arrays or Prefix Sums?

2. In a Fenwick Tree (Binary Indexed Tree), how does index jumping work for updates and queries?

3. For which of the following tasks is a Segment Tree strictly required over a Fenwick Tree?

Practice

Build both from this page's code, then verify against brute force on 1,000 random operations (the standard way to trust any advanced structure you write).
The canon: Range Sum Query – Mutable (LC 307) with each structure; Count of Smaller Numbers After Self (LC 315) with Fenwick + coordinate compression.
Swap the operation: convert the segment tree to range-minimum; explain in one sentence why Fenwick couldn't follow you.
Calibrate: for your next mock, decide in advance the one sentence you'd say if range-queries-with-updates appears: name the structure, the complexity, and the Fenwick-vs-segment choice — then move on. Fluency, not ceremony.

That rounds out the data-structure toolkit. Next in the pattern arc: Sorting & Searching.

Practice — climb the ladder

The trigger: range queries MIXED with point updates. Static array? Prefix sums win. Updates but only prefix queries? Fenwick. Arbitrary ranges? Segment tree.

Practice ladder: Segment & Fenwick Trees0/5 solved

Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.

Warm-up

earn the baseline first

Range Sum Query — ImmutableEasy
Prefix sums — the baseline that makes the fancy trees justify themselves.

Core

now updates arrive

Range Sum Query — MutableMedium
The canonical Fenwick/segment-tree problem — log n update, log n query.
My Calendar IMedium
Interval booking with ordered structure — segment-tree thinking without the tree.

Stretch

counting with order

Count of Smaller Numbers After SelfHard
Fenwick over value space (or merge-sort counting) — the classic inversion counter.
The Skyline ProblemHard
Sweep line + ordered max structure — events in, silhouette out.