L54 · Segment Trees & Fenwick (BIT)

Series: LeetCode — From Basics to Interview-Ready · Session 54 / 65 · Phase 3 · Advanced & specialised

Why this session exists

This is the most skippable session in the track and also the one with the sharpest cliff. Segment trees almost never appear in a standard interview loop. But when the problem is "support range sum queries with point updates, both online, with a hundred thousand of each", there is no clever alternative. A prefix-sum array gives O(1) queries and O(n) updates. A plain array gives O(1) updates and O(n) queries. Both die on a mixed workload. The segment tree is the structure that refuses to be worse than logarithmic at either.

So the goal today is not mastery. The goal is: know that this structure exists, know the shape of the problem it answers, and be able to reconstruct the skeleton under pressure. If you can do that, the one interview in fifty where it matters stops being a wall.

The Fenwick tree — binary indexed tree — is the compressed version. Half the code, a fraction of the memory, but it only supports invertible operations (sums, XOR) and not general ones (min, max, gcd). Learn both, because the Fenwick is what you actually want to write when it applies, and the segment tree is what you fall back to when it does not.

Blank-file warm-up

Five minutes, empty file. Write the recursive segment tree skeleton from memory: build, update, query. Three functions, each about eight lines, each following the same three-case shape (fully outside, fully inside, partially overlapping).

The thing to check is not whether you got the indices right on the first attempt. It is whether you reached for the right shape — recursion over a node with its covered interval, with the three-way overlap test at the top. If you produced that shape, the index arithmetic is a detail you can debug. If you did not, the structure has not consolidated yet.

Pattern anatomy

A segment tree is a binary tree over intervals. The root covers [0, n-1]. Every internal node splits its interval at the midpoint and hands the halves to its two children. Leaves cover single elements. Each node stores the aggregate — sum, min, max, gcd — of its interval.

The invariant: every node's stored value equals the aggregate of its two children's values, and a leaf's value equals the array element it covers. Every operation is defined by how it preserves this.

Because the tree has height about log n, and because any query interval decomposes into at most 2·log n nodes, both query and update are logarithmic.

Store it in a flat array. Node i has children 2i+1 and 2i+2. Allocate 4n slots — that bound is generous but safe for any n, and getting cute with the size is a classic way to produce an index error under pressure.

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.t = [0] * (4 * self.n)
        if self.n:
            self._build(arr, 0, 0, self.n - 1)
 
    def _build(self, arr, node, lo, hi):
        if lo == hi:
            self.t[node] = arr[lo]
            return
        mid = (lo + hi) // 2
        self._build(arr, 2 * node + 1, lo, mid)
        self._build(arr, 2 * node + 2, mid + 1, hi)
        self.t[node] = self.t[2 * node + 1] + self.t[2 * node + 2]
 
    def update(self, i, val, node=0, lo=None, hi=None):
        if lo is None:
            lo, hi = 0, self.n - 1
        if lo == hi:
            self.t[node] = val
            return
        mid = (lo + hi) // 2
        if i <= mid:
            self.update(i, val, 2 * node + 1, lo, mid)
        else:
            self.update(i, val, 2 * node + 2, mid + 1, hi)
        self.t[node] = self.t[2 * node + 1] + self.t[2 * node + 2]
 
    def query(self, l, r, node=0, lo=None, hi=None):
        if lo is None:
            lo, hi = 0, self.n - 1
        if r < lo or hi < l:          # disjoint
            return 0                  # identity for sum
        if l <= lo and hi <= r:       # fully covered
            return self.t[node]
        mid = (lo + hi) // 2
        return (self.query(l, r, 2 * node + 1, lo, mid)
                + self.query(l, r, 2 * node + 2, mid + 1, hi))

Three cases in query, always in this order: disjoint, fully covered, partial. Memorise the order — checking "fully covered" before "disjoint" produces wrong answers on empty intersections.

The Fenwick tree does the same job for sums in a quarter of the code. It exploits the binary representation of indices: node i is responsible for the range ending at i of length i & -i (the lowest set bit).

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)        # 1-indexed internally
 
    def add(self, i, delta):          # i is 0-indexed externally
        i += 1
        while i <= self.n:
            self.t[i] += delta
            i += i & -i               # move to the next responsible node
 
    def prefix(self, i):              # sum of arr[0..i], 0-indexed inclusive
        i += 1
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i               # strip the lowest set bit
        return s
 
    def range_sum(self, l, r):
        return self.prefix(r) - (self.prefix(l - 1) if l else 0)

i & -i is the whole trick. In two's complement, -i is ~i + 1, which flips every bit above the lowest set bit and leaves that bit set. ANDing recovers exactly the lowest set bit. Adding it moves up the tree; subtracting it moves down. Two loops, four lines each.

The cue

Reach for one of these structures when the problem statement has all of these together:

1. Both queries and updates are online and interleaved. If all updates come first, build a prefix-sum array and stop. The structure only earns its complexity when the two operation types alternate.
2. Both operation counts are large — typically both n and the number of operations in the 10⁴–10⁵ range. Below that, the O(n) naive update is fine and simpler code wins.
3. The query is an aggregate over a contiguous range — sum, min, max, gcd, count. Not "the element at index i", not "does this range contain x".
4. A "count of smaller / greater elements" phrasing. This is the disguised one. Counting inversions, counting smaller elements to the right, "how many previous values are less than this" — all of these become Fenwick problems after coordinate compression, because they are prefix counts over a value axis rather than an index axis.
5. The word "mutable" in the title. LeetCode is unusually honest here: "Range Sum Query — Mutable" is telling you exactly what it wants.

Tell 4 is the one worth internalising, because it does not look like a range-query problem at all. The move is: map values to ranks, then sweep the array while maintaining a Fenwick over ranks. Each query "how many seen values are smaller than this one" is a prefix sum.

Guided solve

Range Sum Query — Mutable. Implement a class supporting update(index, val) and sumRange(left, right), both called many times.

Start by naming what fails. A prefix-sum array gives O(1) sumRange but every update invalidates every prefix after it, so updates are O(n). The raw array gives O(1) update but O(n) sumRange. With n and the operation count both around 10⁴, either approach is 10⁸ operations — too slow. Say this before you write code; the interviewer wants to see you rule out the simple options for a stated reason rather than skipping straight to the exotic structure.

Then the structure. Since the aggregate is sum and sums are invertible, Fenwick is the better choice: less code, less memory, fewer places to make a mistake. The only wrinkle is the delta-versus-value issue from the callout — LeetCode's update sets a value, so keep a shadow copy of the array.

class NumArray:
    def __init__(self, nums):
        self.nums = nums[:]                 # shadow copy: Fenwick needs deltas
        self.n = len(nums)
        self.t = [0] * (self.n + 1)
        for i, v in enumerate(nums):
            self._add(i, v)
 
    def _add(self, i, delta):
        i += 1
        while i <= self.n:
            self.t[i] += delta
            i += i & -i
 
    def _prefix(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i
        return s
 
    def update(self, index, val):
        self._add(index, val - self.nums[index])
        self.nums[index] = val
 
    def sumRange(self, left, right):
        return self._prefix(right) - (self._prefix(left - 1) if left else 0)

One thing to mention aloud: the constructor as written is O(n log n) because it does n separate add calls. There is an O(n) construction — fill t[i] with the raw values, then for each i push t[i] into its parent i + (i & -i) — but the log factor on a one-time build is rarely worth the extra code. Knowing it exists is what earns the point.

Sanity-check by hand on [1, 2, 3]: prefix(2) should be 6, update(1, 5) then prefix(2) should be 9. Two checks, ten seconds, catches every index error.

Solo timed

Fifteen minutes each.

• Count of Smaller Numbers After Self — sweep from the right and ask, for each element, how many already-seen values are strictly smaller. Coordinate-compress first: the values can be huge, but there are only n of them, so map each to its rank.

If you finish early, implement the segment tree version of Range Sum Query Mutable as well. Writing both structures for the same problem back to back is the fastest way to internalise what the Fenwick is actually compressing.

Common failure modes

Off-by-one between 0-indexed input and 1-indexed Fenwick. The Fenwick's low-bit arithmetic breaks at index 0 because 0 & -0 == 0, giving an infinite loop. The fix is the i += 1 at the top of both methods. Skip it and the code hangs rather than returning a wrong answer, which at least fails loudly.

Wrong order of the three cases in query. Test disjoint first, then fully-covered, then recurse. Reversing the first two returns garbage whenever the query range and node range do not intersect.

Returning the wrong identity on the disjoint branch. For sum it is 0. For min it is infinity. For max it is negative infinity. For gcd it is 0. Returning 0 from a min-tree's disjoint branch silently makes every query return 0.

Using Fenwick for min or max. It does not work for a general range. The subtraction trick prefix(r) - prefix(l-1) requires an invertible operation, and min has no inverse — you cannot un-min a value. If the aggregate is min, max, or gcd over an arbitrary range, you need a segment tree.

Undersizing the segment tree array. 2n is not enough. 4n always is. Do not try to compute the tight bound during an interview.

Complexity

Segment tree: build is O(n) — each of the roughly 2n nodes is initialised once. Query is O(log n) because the recursion prunes to at most two paths from root to leaf, contributing at most four nodes per level. Update is O(log n), one node per level along a single root-to-leaf path. Space is O(4n) as allocated, of which about 2n is actually used.

Fenwick: update and prefix query are both O(log n) — each loop iteration adds or removes one set bit from the index, and a value under n has at most log n set bits. Space is O(n). Naive construction is O(n log n); the in-place variant is O(n).

Count of Smaller Numbers After Self: O(n log n) total — one Fenwick update and one prefix query per element, plus O(n log n) for the coordinate compression sort.

Spaced queue

Re-solve anything due before starting new material. Status ladder:

• cold — solved unaided and clean → 60 days
• warm — solved with a stumble → 21 days
• hint — needed a nudge → 7 days
• failed — no working solution → 2 days, then 7 days

Be honest about this session in particular. Almost everyone marks segment trees warm when the truth is hint, because the shape felt familiar even though the indices did not come out. Familiarity is not retrieval.