Fenwick Trees & Segment Trees (Range Queries with Updates)

Why this matters more than it seems

Every other tree subtopic in this roadmap works on data that doesn't change while you query it. Real problems (and a specific, recognizable slice of "hard" interview questions) ask for both at once: repeated range queries over an array that is also being updated. A plain prefix-sum array answers range-sum queries in O(1) — but only if the underlying array never changes; a single update forces an O(n) rebuild. This subtopic covers the two structures built specifically to make both operations fast simultaneously: the Fenwick tree (Binary Indexed Tree, or BIT) and the more general segment tree.

This is a more specialized topic than the rest of the roadmap — you're less likely to need it than, say, sliding window or two pointers — but it shows up often enough in "hard"-rated interview questions at the top-tier companies (and constantly in online assessments and competitive programming) that a Senior candidate should recognize the pattern and be able to sketch an implementation, even if it takes a few extra minutes of thought.

The problem, precisely

Given an array, support both of these efficiently, repeatedly, in any order:

Update: change the value at some index.
Query: compute an aggregate (most commonly sum, but also min/max/gcd/xor) over a contiguous range [l, r].

Approach	Update	Range query	Notes
Recompute from scratch each query	O(1)	O(n)	Fine only if queries are rare
Precomputed prefix-sum array	O(n) (must rebuild suffix)	O(1)	Fine only if the array is static
Fenwick tree / segment tree	O(log n)	O(log n)	The answer once both operations are frequent

Recognize this shape from the problem statement: "you are given an array and must process a mix of two types of queries — updates to a single element, and range aggregate queries — efficiently." That phrasing, almost verbatim, is the signal to reach for one of these two structures.

Fenwick Tree (Binary Indexed Tree)

A Fenwick tree stores partial sums in a single array of the same size as your input, using a clever indexing trick based on each index's lowest set bit. It's simpler to code than a segment tree and uses less memory, but it's specialized to operations that have an inverse (sum, XOR) — it cannot directly support range-min or range-max, because you can't "subtract" a minimum back out the way you can subtract a sum.

The key primitive is i & -i (in two's-complement, this isolates the lowest set bit of i), which tells you both how far to jump when updating and how far to jump when querying. Using 1-based indexing (the conventional and least error-prone way to implement this):

class FenwickTree:
    def __init__(self, n: int):
        self.tree = [0] * (n + 1)   # 1-indexed; tree[0] unused

    def update(self, i: int, delta: int) -> None:
        # add `delta` to index i, propagating to every partial-sum bucket that covers it
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & (-i)

    def prefix_sum(self, i: int) -> int:
        # sum of elements [1..i]
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)
        return total

    def range_sum(self, left: int, right: int) -> int:
        # sum of elements [left..right], 1-indexed inclusive
        return self.prefix_sum(right) - self.prefix_sum(left - 1)

Both update and prefix_sum do at most O(log n) work, because i & -i guarantees you only ever visit indices tied to the set bits of i — there are at most log₂(n) of those. Building a Fenwick tree from an existing array of n elements is a loop of n calls to update, giving O(n log n) construction (there's also an O(n) construction trick, but it's rarely necessary to know for interviews).

Segment Tree

A segment tree generalizes the idea to any associative combining function — sum, min, max, gcd, and more — at the cost of being a bit more code and roughly 2–4x the memory of a Fenwick tree. It's a binary tree where each node represents a range of the array, storing the combined value of that range; leaves represent single elements, and each internal node's value is combine(left child, right child).

A compact, array-based implementation (no pointers, no recursion needed for build/query/update) stores the tree bottom-up in a single array of size 2n:

class SegmentTree:
    def __init__(self, data: list[int]):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]   # swap + for min()/max() as needed

    def update(self, i: int, value: int) -> None:
        i += self.n
        self.tree[i] = value
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, left: int, right: int) -> int:
        # sum over [left, right), i.e. right-exclusive — a common convention for this layout
        result = 0
        left += self.n
        right += self.n
        while left < right:
            if left % 2 == 1:
                result += self.tree[left]
                left += 1
            if right % 2 == 1:
                right -= 1
                result += self.tree[right]
            left //= 2
            right //= 2
        return result

Construction is O(n) (build the leaves, then combine upward level by level), and both update and query are O(log n) — each only ever touches one node per level of the tree.

Segment trees also support range updates with lazy propagation (add a value to every element in a range, in O(log n) rather than O(n) per update) — this is a real technique worth knowing exists, but it adds meaningful implementation complexity and is rarely required to implement from scratch in a general Senior SWE interview loop. Recognize the name and the problem shape it solves; don't feel obligated to memorize the implementation unless you're specifically prepping for a company known to go deep here.

Fenwick vs. segment tree — which to reach for

	Fenwick tree	Segment tree
Supports	Sum, XOR (invertible operations)	Any associative operation (sum, min, max, gcd, custom)
Code size	Small (~10 lines)	Larger
Memory	O(n)	O(n) to O(4n) depending on implementation
Range updates + lazy propagation	Awkward, less common	Well-supported, standard extension

Default to a Fenwick tree when the problem is specifically about sums (or XORs) — it's less code and less to get wrong under interview pressure. Reach for a segment tree when the aggregate is min/max/gcd, or when you need range updates in addition to range queries.

Coordinate compression: the trick that unlocks most LeetCode uses of these structures

Both structures index by array position, but a large family of problems actually need to index by value — for example, "as I scan left to right, how many previously-seen values are smaller than the current one?" Values can be arbitrarily large, negative, or sparse, so you can't allocate a Fenwick tree sized to the value range directly.

Coordinate compression fixes this: take all values that will ever be inserted, sort and de-duplicate them, and map each value to its rank (position in that sorted list). Use the rank — always a small, dense integer starting near 0 or 1 — as the Fenwick tree index instead of the raw value.

def compress(values: list[int]) -> dict[int, int]:
    sorted_unique = sorted(set(values))
    return {v: i + 1 for i, v in enumerate(sorted_unique)}   # 1-indexed ranks for the Fenwick tree above

Worked pattern: counting smaller elements with a Fenwick tree

"Count of Smaller Numbers After Self" is the canonical problem this unlocks. For each index, you need to know how many elements to its right are smaller than it — naively O(n²). The Fenwick-tree approach: scan right to left, and for each element, query how many smaller elements have been inserted so far (which, since you're going right-to-left, means "to the right of the current element"), then insert the current element.

def count_smaller(nums: list[int]) -> list[int]:
    rank = compress(nums)
    bit = FenwickTree(len(rank))
    result = [0] * len(nums)

    for i in range(len(nums) - 1, -1, -1):
        r = rank[nums[i]]
        result[i] = bit.prefix_sum(r - 1)   # count of ranks strictly smaller than nums[i]'s rank
        bit.update(r, 1)                     # record that this value has now been "seen"

    return result

Every one of the n elements does one O(log n) query and one O(log n) update, for O(n log n) total — versus O(n²) for the brute-force nested-loop approach. This exact shape (coordinate-compress, then scan while querying/updating a Fenwick tree indexed by rank) also solves "Count of Range Sum" and "Reverse Pairs" with only minor changes to what's being counted.

Recognizing when to reach for these

The problem explicitly says it will "handle multiple queries" of an update type and a range-query type, interleaved, on a mutable array.
"Count the number of elements smaller/larger/within a range, relative to elements seen so far" while scanning — a strong signal for coordinate compression + Fenwick tree.
Anything phrased as "range sum/min/max query, mutable array" — read "mutable" as an explicit hint that a plain prefix-sum array (O(n) rebuild per update) won't meet the time limit.

Pitfalls and interview gotchas

Off-by-one between 0-indexed and 1-indexed. The classic Fenwick tree implementation is 1-indexed internally (index 0 is deliberately unused, since 0 & -0 == 0 would infinite-loop the traversal) — convert your problem's 0-indexed positions to 1-indexed before calling update/prefix_sum. This single mismatch is the most common bug in Fenwick tree code.
Reaching for a Fenwick tree for min/max. It only works cleanly for operations with an inverse (you can "undo" a sum by subtracting; you cannot "undo" a min). Use a segment tree for min/max/gcd-style aggregates instead.
Forgetting to coordinate-compress before indexing by value. Using a raw value as a Fenwick tree index when values can be large or negative either crashes (index out of bounds) or wastes enormous memory allocating an array sized to the value range instead of the element count.
query(left, right) bounds conventions. The segment tree implementation above uses right-exclusive ranges ([left, right)), while the Fenwick tree's range_sum uses inclusive [left, right]. Pick one convention per structure and be explicit about it — mixing the two mid-solution is a frequent source of off-by-one bugs.
Building a segment tree recursively when you don't need to. The bottom-up array-based construction shown above avoids recursion entirely and is simpler to get right under time pressure than the classic recursive-with-pointers version; prefer it unless the problem specifically needs range updates with lazy propagation, which is easier to express recursively.

How to state this in an interview

"Since we need to interleave point updates with range-sum queries on the same array, I'll use a Fenwick tree — each operation costs O(log n), which beats maintaining a plain prefix-sum array, where an update would force an O(n) rebuild. If the aggregate here were min or max instead of sum, I'd reach for a segment tree instead, since Fenwick trees only work cleanly for invertible operations."

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Range Sum Query - MutableMedium!3/530m

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.

Count of Smaller Numbers After SelfHard~5/545m
Count of Range SumHard~5/545m
Dynamic Range Sum QueriesCSES~2/525m
Dynamic Range Minimum QueriesCSES~3/530m
Range Sum Query 2D - MutableHardPremium~4/540m
Reverse PairsHard~4/540m