Segment Trees & Fenwick (BIT)

Review boundary and corrected contracts

The size is a nonnegative integer; external indices are zero-based and range endpoints inclusive. Fenwick.prefix(-1) is the empty prefix and returns zero; other invalid indices raise, including in the NumArray wrapper. SegmentTree’s optional recursion parameters are internal plumbing: callers use update(i, value) and query(l, r). The old valid-index algorithms were correct; adding guards extends their invalid-input contract. Prefix differences require inverses, whereas a segment tree needs an associative combine and an identity.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Be able to build a segment tree and a Fenwick tree from a blank file, and — more importantly — recognise the narrow class of problems where nothing simpler will do.

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

Why this session exists

For mixed online point updates and range aggregation, choose among a segment tree, Fenwick tree (when its algebra applies), or other workload-appropriate structures. Prefix sums and naive arrays are important baselines; none is a universal winner.

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, a review that requires online aggregation becomes a problem you can reason through rather than a memorisation test.

The Fenwick tree — binary indexed tree — uses overlapping prefix blocks rather than a segment tree’s explicit interval hierarchy. The sum implementation below is compact and uses n+1 slots. Its arbitrary-range query subtracts two prefixes, which needs an inverse. This does not mean every Fenwick variant requires an inverse: prefix minimum with only decreasing point updates is a useful restricted variant. General arbitrary updates and arbitrary-range min/max/gcd are better served by a segment tree.

Blank-file warm-up

Five minutes, empty file. Write the recursive segment tree skeleton from memory: build, update, query. Build combines two children, update follows one root-to-leaf path, and query uses the three overlap cases (disjoint, fully covered, partial). Only query has that three-case overlap shape.

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:
            if not 0 <= i < self.n:
                raise IndexError(i)
            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:
            if not 0 <= l <= r < self.n:
                raise IndexError((l, r))
            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: disjoint returns the identity, full coverage returns the stored aggregate, and partial coverage recurses. For valid nonempty ranges the first two predicates are mutually exclusive; swapping their checks does not inherently produce a wrong answer.

The Fenwick tree does the same job for sums in a quarter of the code, but its stored blocks are laid out differently from the segment tree's explicit halves. 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). Picture the internal, one-based index 12: its block contains positions 9 through 12. A prefix query takes that block, then continues at 8 to collect positions 1 through 8, with no overlap. An update travels the other way, adding its delta to every stored block that contains the changed position. The add/subtract low-bit loops below navigate those blocks; they are not movements through individual array elements.

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
        if not 0 <= i < self.n:
            raise IndexError(i)
        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
        if not -1 <= i < self.n:
            raise IndexError(i)
        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):
        if not 0 <= l <= r < self.n:
            raise IndexError((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.

Fenwick accepts deltas; its nodes store block aggregates

add(i, delta) adds to the existing value; it does not set it. If the problem gives you set(i, val), you must track the current array separately and call add(i, val - current[i]). Forgetting this is a Fenwick bug, and it produces answers that are subtly and increasingly wrong rather than obviously broken.

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. Many queries and updates need to be cheap. A raw array makes point assignment O(1) but range sum O(n); a prefix array reverses that trade. Estimate the total operations for your actual mix rather than treating a fixed input-size threshold as a timing guarantee.
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 the baseline tradeoffs. A prefix-sum array gives O(1) sumRange but a point update can invalidate O(n) stored prefixes. A raw array gives O(1) update but up to O(n) range sum. With 10⁴ expensive operations over 10⁴ entries, either baseline can require about 10⁸ element operations. That work estimate motivates a tree; it is not a measured timeout claim.

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):
        if not 0 <= index < self.n:
            raise IndexError(index)
        self._add(index, val - self.nums[index])
        self.nums[index] = val
 
    def sumRange(self, left, right):
        if not 0 <= left <= right < self.n:
            raise IndexError((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]: sumRange(0, 2) is 6; after update(1, 5) it is 9. Then test a one-element range, negative values and invalid endpoints. Two examples are useful smoke tests, not a guarantee against 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.

Confusing case order with case coverage. For a valid node interval and a valid query, disjoint and fully contained cannot both hold. You may check either first. What matters is returning the identity for disjoint nodes, returning the stored aggregate for full coverage, and recursing only on partial overlap. Reversing the first two correct tests does not create a counterexample.

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 can incorrectly beat a positive minimum on a partial-range query; a fully covered root need not visit that branch.

Using prefix minima as if they were invertible. From two prefix minima you cannot recover a general subrange minimum. A restricted Fenwick prefix-min structure can support decreasing updates, but that is a different contract from arbitrary assignment and arbitrary-range minimum. Use a segment tree for the latter.

Undersizing this recursive layout. 2n is not a universal bound for midpoint recursion with children 2i+1 and 2i+2; 4n is safe. An iterative segment tree can use a different 2n-slot layout, so the size rule belongs to the implementation, not the abstract data structure.

Myth: A segment tree is just a fancier prefix-sum array, so I can always use whichever I remember better.

Why: They have opposite cost profiles. A prefix-sum array is O(1) query and O(n) update — it assumes the data is static after construction. A segment tree is O(log n) for both — it assumes the data changes. On a read-only workload the prefix array wins outright and the tree is pure overhead. On a mixed workload with many interleaved updates the prefix array degrades to quadratic total time. They are not interchangeable; the deciding question is whether updates happen after queries begin.

Steps 1: A range aggregate over a contiguous interval can be assembled from aggregates of any set of disjoint sub-intervals that exactly tile it.

Steps 2: Because that is true, we are free to precompute aggregates for a fixed family of intervals and answer queries by combining a subset of them.

Steps 3: Because we want any query interval to be tileable by few precomputed intervals, the family should be hierarchical — halve repeatedly, so the depth is logarithmic even when n is not a power of two.

Steps 4: Because the hierarchy has depth log n, and any interval's left and right boundaries each cut at most one node per level, at most about 2·log n precomputed intervals are needed per query.

Steps 5: Because each array element belongs to exactly one node per level, a point update touches exactly one node per level — also log n.

Steps 6: Both operations visit O(log n) levels, while repeated prefix-array repairs can touch O(n) entries per update. This is a bound on work, not a promise that a million operations finish in a stated number of seconds.

Picture: A company org chart where every manager's number is the sum of their direct reports' numbers. Change one employee's number and you walk up your reporting chain fixing each manager — one per level. Ask for a department total and you grab the few managers who exactly cover it rather than summing every individual.

Trigger: Fires when a problem needs both 'change one value' and 'aggregate a range', repeatedly and interleaved.

Name: Fenwick tree (BIT)

Gain: About fifteen lines total; n+1 memory; excellent constant factor; nearly impossible to get the structure wrong once the low-bit trick is memorised

Cost: This sum/XOR range-query design needs invertible prefix aggregates. Range-add/point-query can use one Fenwick over a difference array; range-add/range-sum can use two. Neither is implemented by simply passing an interval to add.

Name: Segment tree

Gain: Handles any associative aggregate; extends to lazy propagation for range updates; the recursive structure mirrors the problem so it is easier to reason about

Cost: Four times the memory, three to four times the code, and more index arithmetic to get wrong under a timer

Pick: Fenwick for point deltas and sum/XOR/count queries. Segment trees handle general associative range aggregates and, with suitable lazy tags, range updates. For range-add/range-sum specifically, two Fenwick trees are also an option; range updates alone do not force a segment tree.

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 prefix queries remove the lowest set bit each time. Updates add the lowbit: trailing set bits may clear and a higher bit becomes set, so the lowest set-bit position strictly rises. Both loops take O(log n) iterations. Storage is O(n); repeated-add construction is O(n log n), while the parent-accumulation construction 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.

Self-check (answer follows each question).

Q: Why does a Fenwick tree work for sums but not for range minimum?

A: Range queries are answered by subtracting one prefix from another, which requires the aggregate to have an inverse. Addition does; min does not — there is no operation that removes a value from a computed minimum.

Q: What does i & -i compute, and why is it the core of the Fenwick tree?

A: It isolates the lowest set bit of i. In two's complement, -i flips all bits above the lowest set bit, so the AND leaves exactly that bit. Adding it moves to the next node responsible for a larger range; subtracting it moves to the previous disjoint block.

Q: In the segment tree query, what are the three cases and in what order must they be checked?

A: Disjoint returns the identity; fully covered returns the stored aggregate; partial overlap recurses and combines. The first two are mutually exclusive for valid nonempty intervals, so either may be checked first. Both must precede the partial-overlap recursion.

Q: Why allocate 4n rather than 2n for the segment tree array?

A: In this recursive array layout, midpoint splits can leave holes in the implicit heap indexing and require indices beyond 2n. The binary tree has 2n−1 actual nodes for n positive leaves, but its largest occupied index can be larger. Allocating 4n is safe; a different iterative layout can use 2n.

Q: How does 'Count of Smaller Numbers After Self' become a Fenwick problem?

A: Coordinate-compress the values to ranks, then sweep right to left maintaining a Fenwick over ranks. For each element, the answer is the prefix sum over ranks strictly below its own — the count of already-seen smaller values.

Q: You need range sum queries AND range updates (add a value to every element in a range). Which structure, and what does it need on top?

A: A segment tree with lazy propagation — updates are stored as pending deltas at the highest fully-covered nodes and pushed down only when a later query needs to descend past them. Alternatively two Fenwick trees using the range-update/range-query decomposition, which is less code but harder to derive on the spot.

Stretch: true

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.

• Frequent interleaved point updates and range queries motivate these structures. Static queries may have simpler solutions; coordinate-counting and range-update variants are additional workloads, not exceptions that invalidate the structure.

• The segment tree invariant is that every node equals the combination of its children — every operation is defined by preserving it.

• Query has three mutually exclusive cases: disjoint, full coverage and partial overlap; recurse only in the third.

• The displayed Fenwick arbitrary-range sum uses invertible prefixes. Restricted prefix-min variants exist; general min/max/gcd range aggregation with arbitrary updates calls for a different structure such as a segment tree.

• i & -i isolates the lowest set bit; add it to climb, subtract it to descend. That single expression is the whole Fenwick.

• 'Count of smaller elements' problems are Fenwick problems in disguise — compress values to ranks and treat the value axis as the index axis.

Corrective source notes

• Fenwick Tree - Algorithms for Competitive Programming — A Fenwick tree supports range sums with logarithmic update/query operations and linear storage. Checked 2026-10-07.
• Segment Tree - Algorithms for Competitive Programming — A sum segment-tree internal node merges its two children by addition, and leaves store individual array values. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.