Fenwick Tree (Binary Indexed Tree) — Comprehensive Guide

A Fenwick tree — also called a Binary Indexed Tree (BIT) — gives prefix aggregates with point updates in O(log N) using one flat array and a single bit trick. It does less than a segment tree but with far less code and a smaller constant factor. When your aggregate is invertible (sum, xor) and you need point-update + prefix/range-query, the BIT is the right tool.

Quick Navigation: “I need to…”

Table of Contents

1. Why a Fenwick Tree
2. Basic Fenwick Tree
3. The lowbit Trick
4. The Invertibility Requirement
5. Range Update, Point Query
6. Range Update, Range Query
7. Binary Search on a BIT
8. 2D Fenwick Tree
9. Common Patterns Collection
10. Worked LeetCode Problems
11. Fenwick vs Segment Tree
12. Pattern Recognition Cheat Sheet

1. Why a Fenwick Tree

You need prefix sums and updates, interleaved:

Concretely: you have an array and must process 10^5 interleaved update(i, x) and sumRange(l, r) operations. A prefix-sum array answers each query in O(1) but every update forces an O(N) rebuild; a plain array updates in O(1) but each sum is O(N) — both are O(N·Q) overall and blow up. The BIT makes both operations O(log N), so the whole workload is O(Q log N).

Fenwick and segment tree have the same asymptotic cost. The Fenwick wins on code size (≈10 lines) and constant factor (one array, no recursion, cache-friendly). It loses on generality: it can only do invertible aggregates (Section 4).

The cleanest way to hold the relationship in your head: a Fenwick tree is the segment tree you get to skip building when the operation is invertible. A segment tree needs explicit nodes because it must answer [l, r] directly. If the operation has an inverse, you never need [l, r] directly — you get it as prefix(r) − prefix(l−1). That single concession removes the need to store children, navigate down from a root, or handle a general range at all. What is left is the i ± lowbit(i) index arithmetic below, which is the tree, walked implicitly.

The Idea

Index i (1-based) is responsible for a range of length lowbit(i) ending at i, where lowbit(i) = i & (-i) is the lowest set bit. A prefix sum walks down by stripping lowest bits; an update walks up by adding them.

Responsibility ranges (1-indexed, n=8):

 idx:  1   2   3   4   5   6   7   8
 bit:  1  10  11 100 101 110 111 1000
 len:  1   2   1   4   1   2   1    8

 tree[1] covers a[1]
 tree[2] covers a[1..2]
 tree[3] covers a[3]
 tree[4] covers a[1..4]
 tree[6] covers a[5..6]
 tree[8] covers a[1..8]

Where the lowbit rule comes from

That table looks arbitrary until you see it is forced, not chosen. Start from the requirement and the lowbit rule falls out.

The requirement. Every prefix a[1..k] must be expressible as a sum of a few stored blocks. Write k in binary and peel its set bits from the top: k = 11 = 1011₂ = 8 + 2 + 1, so

a[1..11]  =  a[1..8]  +  a[9..10]  +  a[11]
             ^^^^^^^     ^^^^^^^^     ^^^^^
             8 = 1000    2 = 10       1 = 1     block lengths are exactly k's set bits

Each block ends at a running total of the bits consumed so far — 8, then 8+2 = 10, then 8+2+1 = 11. So if we store each block at the index where it ends, the block ending at index i has length equal to i’s lowest set bit. That is the rule: tree[i] covers a[i - lowbit(i) + 1 .. i]. It is not a clever trick someone invented; it is the unique layout that makes binary decomposition of a prefix work.

Both walks are now determined. Reading prefix(k) means consuming k’s set bits from the bottom, and k -= lowbit(k) does exactly that — 11 → 10 → 8 → 0, summing tree[11] + tree[10] + tree[8], which is the three blocks above.

Updating a[i] must touch every block containing i. Those are found by i += lowbit(i): from i = 5 you get 5 → 6 → 8, and indeed tree[5] covers a[5], tree[6] covers a[5..6], and tree[8] covers a[1..8] — the three blocks containing index 5, and no others.

The two walks move in opposite directions because they answer opposite questions: which blocks tile this prefix (strip bits) versus which blocks contain this index (add bits). Both consume at most one bit position per step, so both are O(log n).

Master LeetCode Comparison Table

The BIT shows up on LeetCode whenever you need updates interleaved with prefix/range queries, or the classic “count elements with property X seen so far” sweep. The worked problems in §9.5 map to these:

The split is stark: 307 indexes by position (the array is the data); everything else indexes by value (the BIT counts occurrences along a value axis you compress first). Spotting which axis you’re on is the whole battle.

2. Basic Fenwick Tree

Point update, prefix sum, range sum. 1-indexed internally; the API below takes 0-indexed positions.

Reading the examples: the diagrams and walks in this guide show the internal 1-indexed tree[]; the code’s public methods take 0-indexed positions and do i += 1 at the boundary. So a 0-indexed position p in the API maps to internal index p + 1.

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

    def update(self, i, delta):        # a[i] += delta  (0-indexed i)
        i += 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)              # move to next responsible index (add lowbit)

    def prefix(self, i):               # sum of a[0..i]  (0-indexed i)
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)              # strip lowbit, jump to previous range
        return s

    def range_sum(self, l, r):         # sum of a[l..r] inclusive
        return self.prefix(r) - (self.prefix(l - 1) if l > 0 else 0)

Build in O(N)

Naive build is N updates = O(N log N). Linear build: add each value to its parent.

Note — this is a method on the BIT class above, not standalone code. The indentation is deliberate: paste it inside the class body.

    @classmethod
    def from_array(cls, data):
        bit = cls(len(data))
        for i, v in enumerate(data):
            bit.tree[i + 1] += v
        for i in range(1, bit.n + 1):
            j = i + (i & (-i))
            if j <= bit.n:
                bit.tree[j] += bit.tree[i]
        return bit

Complexity

Worked Trace on Real Values

Take a = [3, 2, -1, 5] (0-indexed). After building, the internal 1-indexed tree[] holds each index’s responsibility range:

 internal idx:  1   2   3   4
 covers:       a[0] a[0..1] a[2] a[0..3]
 tree[]:        3    5     -1    9

 tree[1] = a[0]              = 3
 tree[2] = a[0] + a[1]       = 3 + 2       = 5
 tree[3] = a[2]              = -1
 tree[4] = a[0]+a[1]+a[2]+a[3] = 3+2-1+5   = 9

Now prefix(2) (0-indexed → sum of a[0..2] = 3 + 2 + (-1) = 4). The code does i += 1, so it descends from internal index 3:

i = 3 (011): add tree[3] = -1      strip lowbit(1) -> i = 2
i = 2 (010): add tree[2] =  5      strip lowbit(2) -> i = 0  stop

sum = tree[3] + tree[2] = -1 + 5 = 4  ✓  (matches a[0]+a[1]+a[2])

3. The lowbit Trick

lowbit(i) = i & (-i) isolates the lowest set bit. Two’s complement makes -i flip-all-bits-plus-one, so i & -i leaves only that lowest 1.

 i      = 12 = 0000 1100
-i      =      1111 0100   (two's complement)
 i & -i = 0000 0100 = 4    (the lowbit)

The Two Walks

UPDATE (climb): i += lowbit(i)
  a[6] changes (0-indexed) -> internal index 7 (a[6] maps to i = 6 + 1 = 7)
  7 -> 8 -> (past n, stop)

QUERY (descend): i -= lowbit(i)
  prefix up to index 7:
  7 (0111) -> strip -> 6 (0110) -> strip -> 4 (0100) -> strip -> 0 stop
  tree[7] + tree[6] + tree[4]  = a[7] + a[5..6] + a[1..4]  = a[1..7]  ✓

Update adds lowbit (goes to the wider range containing you); query subtracts lowbit (jumps to the previous disjoint chunk). The two are exact inverses of each other — that symmetry is why 10 lines suffice.

4. The Invertibility Requirement

Range query is prefix(r) - prefix(l-1). That subtraction is mandatory: a BIT can only answer a range if the operation has an inverse.

Prefix XOR Variant

Same code, swap + for ^ and identity stays 0 (xor is its own inverse).

class XorBIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, val):          # a[i] ^= val
        i += 1
        while i <= self.n:
            self.tree[i] ^= val
            i += i & (-i)

    def prefix_xor(self, i):
        i += 1; x = 0
        while i > 0:
            x ^= self.tree[i]
            i -= i & (-i)
        return x

    def range_xor(self, l, r):
        return self.prefix_xor(r) ^ (self.prefix_xor(l - 1) if l > 0 else 0)

★ Insight ───────────────────────────────────── This is the single most important “when to use” line: min/max/gcd have no inverse, so a plain BIT cannot do range-min/max — reach for a segment tree instead. (There is a max-BIT that supports prefix-max with point-increase-only updates, but it can’t do arbitrary decreases or true range-max. Don’t force it.) ─────────────────────────────────────────────────

5. Range Update, Point Query

Flip the roles using a difference array stored in a BIT. To add x to a[l..r]: diff[l] += x, diff[r+1] -= x. Then a[i] = prefix_sum(diff, i).

class RangeUpdateBIT:
    def __init__(self, n):
        self.bit = BIT(n)
        self.n = n

    def range_add(self, l, r, x):      # a[l..r] += x
        self.bit.update(l, x)
        if r + 1 < self.n:
            self.bit.update(r + 1, -x)

    def point_query(self, i):          # value at a[i]
        return self.bit.prefix(i)      # prefix of the difference array = current value

Query is now the point value, update is the range. Mirror image of the basic BIT.

6. Range Update, Range Query

The two-BIT trick. Support both range-add and range-sum in O(log N). Derived from expanding the difference-array prefix sum algebraically.

Let d be the difference array (d[l]+=x, d[r+1]-=x). Then:

sum(a[1..i]) = sum_{k=1..i} ( (i+1) * d[k]  -  k * d[k] )
             = (i+1) * prefix(B1, i)  -  prefix(B2, i)

where B1 tracks d[k], B2 tracks k*d[k].

class RangeRangeBIT:
    def __init__(self, n):
        self.n = n
        self.b1 = BIT(n)               # tracks d[k]
        self.b2 = BIT(n)               # tracks k * d[k]

    def range_add(self, l, r, x):      # a[l..r] += x  (0-indexed inclusive)
        self.b1.update(l, x)
        if r + 1 < self.n: self.b1.update(r + 1, -x)
        self.b2.update(l, x * l)
        if r + 1 < self.n: self.b2.update(r + 1, -x * (r + 1))

    def prefix(self, i):               # sum a[0..i]
        return (i + 1) * self.b1.prefix(i) - self.b2.prefix(i)

    def range_sum(self, l, r):
        return self.prefix(r) - (self.prefix(l - 1) if l > 0 else 0)

This does what a lazy segment tree does (range add + range sum) in ~half the code — but only for invertible aggregates. For range-assign or range-min, you still need the segment tree.

7. Binary Search on a BIT

Find the smallest index whose prefix sum reaches k in a single O(log N) descent — no O(log²N) query-in-a-binary-search. Walk bits from high to low.

def find_kth(bit, k):
    """Smallest 0-indexed i with prefix(i) >= k. Assumes non-negative values."""
    pos = 0
    log = bit.n.bit_length()
    for b in range(log, -1, -1):
        nxt = pos + (1 << b)
        if nxt <= bit.n and bit.tree[nxt] < k:
            pos = nxt
            k -= bit.tree[nxt]
    return pos            # 0-indexed answer is pos (1-indexed pos+1)

Classic use: value-indexed BIT of counts → find_kth returns the k-th smallest value present. Same job as the segment-tree descent, fewer lines.

8. 2D Fenwick Tree

Point update + prefix-rectangle sum on a grid, in O(log M · log N). Nest the climb/descend in both dimensions.

class BIT2D:
    def __init__(self, rows, cols):
        self.R, self.C = rows, cols
        self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]

    def update(self, r, c, delta):     # grid[r][c] += delta (0-indexed)
        i = r + 1
        while i <= self.R:
            j = c + 1
            while j <= self.C:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)

    def prefix(self, r, c):            # sum of grid[0..r][0..c]
        s = 0
        i = r + 1
        while i > 0:
            j = c + 1
            while j > 0:
                s += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return s

    def rect_sum(self, r1, c1, r2, c2):   # inclusive rectangle
        return (self.prefix(r2, c2) - self.prefix(r1 - 1, c2)
                - self.prefix(r2, c1 - 1) + self.prefix(r1 - 1, c1 - 1))

Inclusion-exclusion on four prefix rectangles gives the submatrix sum — same shape as the 2D prefix-sum formula, but now updatable.

9. Common Patterns Collection

Count Inversions

Sweep right-to-left over value-ranks; each element asks “how many already-seen values are smaller.”

This guide is canonical for the counting / order-statistics family (LC 315, LC 493, CSES Inversions). Segment Tree §7 shows the same sweep on a segment tree — worth reading only if you already have one built for another part of the problem.

def count_inversions(arr):
    order = sorted(set(arr))
    rank = {v: i for i, v in enumerate(order)}
    bit = BIT(len(order))
    inv = 0
    for x in reversed(arr):
        r = rank[x]
        inv += bit.prefix(r - 1) if r > 0 else 0   # smaller values seen so far
        bit.update(r, 1)
    return inv

Count of Smaller Numbers After Self

Same sweep, collect per-element instead of summing.

Dynamic Range Sum (CSES)

Basic BIT (Section 2) — read point updates and range queries, dispatch.

Range Add + Range Sum (CSES “Range Update Queries”)

Two-BIT trick (Section 6).

K-th Remaining Element

Value/position BIT of 1s + find_kth descent (Section 7); set leaf to 0 on removal.

9.5 Worked LeetCode Problems

Three problems, worked end to end: one position-indexed, two value-indexed. Every solution below was executed against the LeetCode sample cases before publishing.

Problem 307 — Range Sum Query - Mutable

Difficulty: Medium

Given an integer array nums, support two operations, interleaved and many times: update(index, val) sets nums[index] = val, and sumRange(left, right) returns the sum of nums[left..right] inclusive.

This is the BIT’s reason to exist stated as a LeetCode problem: a prefix-sum array would answer sumRange in O(1) but every update costs O(N) to rebuild; a plain array flips the costs. The BIT makes both O(log N).

The only wrinkle over the §2 template: update on LeetCode is an assignment (nums[index] = val), but a BIT stores deltas. So convert: the delta to apply is val - nums[index], and you must keep a plain copy of nums to know the old value.

class NumArray:
    def __init__(self, nums):
        self.nums = nums[:]                 # keep current values to compute deltas
        self.bit = BIT(len(nums))
        for i, v in enumerate(nums):
            self.bit.update(i, v)

    def update(self, index, val):
        delta = val - self.nums[index]      # assignment → delta
        self.nums[index] = val
        self.bit.update(index, delta)

    def sumRange(self, left, right):
        return self.bit.range_sum(left, right)

Trace on nums = [1, 3, 5]:

sumRange(0, 2) = prefix(2) - prefix(-1) = 9 - 0 = 9   ✓
update(1, 2):  delta = 2 - 3 = -1  → bit.update(1, -1)   (nums now [1,2,5])
sumRange(0, 2) = 8                                     ✓

★ Insight ─────────────────────────────────────

• The assignment-vs-delta gap is the single most common 307 bug: calling bit.update(index, val) instead of bit.update(index, val - old) silently corrupts every later sum. A BIT never stores absolute values — always feed it the change.
• The shadow self.nums copy is O(N) extra space but unavoidable with a delta structure: the BIT alone cannot tell you the current value at a point in O(1) (that would be a range_sum(i, i), still O(log N)), and you need the old value before overwriting it. ─────────────────────────────────────────────────

Problem 315 — Count of Smaller Numbers After Self

Difficulty: Hard

Given an integer array nums, return a new array counts where counts[i] is the number of elements to the right of nums[i] that are smaller than nums[i].

Nothing about this says “prefix sum” — but “how many smaller elements to the right” is exactly a value-axis count if you sweep right to left. Process elements from the end; before inserting each value, ask the BIT “how many already-inserted values are strictly smaller than me?” Everything already inserted is, by construction, to the right.

The BIT is indexed by value rank, not array position. Compress values to ranks 0..m-1 first so the value axis is dense.

def countSmaller(nums):
    order = sorted(set(nums))
    rank = {v: i for i, v in enumerate(order)}
    bit = BIT(len(order))
    res = [0] * len(nums)
    for i in range(len(nums) - 1, -1, -1):     # right to left
        r = rank[nums[i]]
        res[i] = bit.prefix(r - 1) if r > 0 else 0   # count of strictly-smaller seen
        bit.update(r, 1)                              # register this value
    return res

Trace on nums = [5, 2, 6, 1] (ranks: 1→0, 2→1, 5→2, 6→3):

i=3 val=1 (r=0): prefix(-1)=0 → res[3]=0; insert rank 0
i=2 val=6 (r=3): prefix(2)=1  → res[2]=1; insert rank 3   (only 1 seen, it's smaller)
i=1 val=2 (r=1): prefix(0)=1  → res[1]=1; insert rank 1   (1 is smaller; 6 is not)
i=0 val=5 (r=2): prefix(1)=2  → res[0]=2; insert rank 2   (1 and 2 are smaller)

res = [2, 1, 1, 0]  ✓

★ Insight ─────────────────────────────────────

• The right-to-left sweep is what makes “to the right” free: at the moment you process index i, the BIT contains exactly the elements to its right. Direction of the sweep encodes the “after self” constraint — no explicit position check needed.
• prefix(r - 1) counts values with rank strictly less than nums[i]. Use r - 1, not r, or you’d count equal values as smaller. This ±1 on the query bound is where “smaller” vs “smaller-or-equal” problems diverge.
• Coordinate compression (sorted(set(...))) keeps the BIT size at O(distinct values) instead of O(max value) — essential when values are large or negative (as -1 here). ─────────────────────────────────────────────────

Problem 493 — Reverse Pairs

Difficulty: Hard

Count pairs (i, j) with i < j and nums[i] > 2 · nums[j].

Same value-indexed BIT, but with a twist that trips people up: the comparison value (2·nums[j]) is different from the value you insert (nums[j]). Sweep left to right; for each j, the BIT holds all earlier elements, and you ask “how many of them exceed 2·nums[j]?”

Because 2·nums[j] may not be one of the array’s values, you can’t look it up by rank directly — use bisect to find where it would sit in the compressed order.

from bisect import bisect_left, bisect_right

def reversePairs(nums):
    order = sorted(set(nums))
    bit = BIT(len(order))
    count = 0
    inserted = 0
    for j in range(len(nums)):
        x = 2 * nums[j]
        idx = bisect_right(order, x)                    # ranks [0..idx-1] hold values ≤ x
        le_count = bit.prefix(idx - 1) if idx > 0 else 0
        count += inserted - le_count                    # the rest are strictly greater
        rj = bisect_left(order, nums[j])
        bit.update(rj, 1)                               # insert nums[j] at its own rank
        inserted += 1
    return count

★ Insight ─────────────────────────────────────

• The query value and the insert value live on the same compressed axis but need not be the same number. bisect_right(order, 2·nums[j]) maps an arbitrary threshold onto that axis without requiring it to be a real element — the reusable trick for any “count elements past a scaled/shifted threshold” problem.
• “Strictly greater than x” is computed as inserted - (count ≤ x). Complementing against the running insert count is cleaner than a suffix query and avoids a second prefix call — the same complement trick that turns “at least k” into “total minus fewer than k” everywhere. ─────────────────────────────────────────────────

10. Fenwick vs Segment Tree

The core decision this guide exists to answer.

Decision Flow

Need range min / max / gcd?            -> Segment tree (BIT can't invert)
Need range ASSIGN (set all = x)?       -> Segment tree (lazy)
Need persistence / historical query?   -> Segment tree (persistent)
Just sum/xor + point or range updates? -> BIT  (shorter, faster)
2D point update + rectangle sum?       -> 2D BIT

Summary: reach for the BIT first when the operation is sum/xor — it’s less code and faster. The moment you hit min/max/gcd, range-assign, or persistence, switch to a segment tree.

11. Pattern Recognition Cheat Sheet

By Problem Signal

The Two Lines You Must Memorize

i += i & (-i)   # UPDATE: climb to the wider range containing i
i -= i & (-i)   # QUERY:  descend to the previous disjoint chunk

Common Pitfalls

Complexity Summary

Practice Order

Start here
    │
    ▼
  Dynamic Range Sum (CSES, Easy)  ──── Basic BIT: point update + range query (§2)
    │
    ▼
  Range Update Queries (CSES)     ──── Two-BIT trick: range add + range sum (§6)
    │
    ▼
  Count Inversions (LC 315 / CSES) ─── Value-indexed BIT: count smaller-so-far (§9)
    │
    ▼
  Reverse Pairs (LC 493, Hard)    ──── Same BIT, but the query bound is 2*x (§9)
    │
    ▼
  K-th / order-statistic descent  ──── find_kth: one O(log N) bit walk (§7)
    │
    ▼
  2D BIT (Hard)                   ──── Nest the walk in both dims + inclusion-exclusion (§8)

When This Fails

A Fenwick tree answers query(l, r) as prefix(r) − prefix(l−1), so it lives or dies by invertibility:

• Non-invertible aggregates. Min, max, and gcd cannot be recovered by subtraction. A “max BIT” exists but only supports prefix maxima with increase-only updates — it cannot do arbitrary range max. Use a segment tree.
• Zero-indexing. The i & -i walk requires 1-based indices; index 0 makes lowbit zero and the loop never terminates. Always offset by one internally.
• Value-indexed use without compression. Indexing by raw value needs an array the size of the value range. Compress to ranks first.
• No updates at all. A prefix sum is O(1) per query. Do not build a BIT for static data.
• Confusing the two axes. Indexing by position answers “sum of a range of positions”; indexing by value rank answers “how many values below x”. Mixing them up is the most common bug in this family.

Self-Test

Answer these from memory, out loud or on paper, before looking. Recognition is not recall: rereading an explanation feels like knowing, and it is not. A question you cannot answer cold names the exact section to revisit — you do not need to reread the guide.

1. What does i & -i compute, and why is it the whole data structure?

2. Which direction does update walk, and which direction does query?

3. Why must a Fenwick tree be 1-indexed?

4. What can a BIT do that people assume it cannot?

5. What is the k-th element descent, and why is it O(log n) rather than O(log² n)?

6. How do you count inversions with a BIT?

7. Can you build a BIT in O(n)?

8. Position-indexed or value-indexed — which do you need?

See Also

• Segment Tree Patterns — when you need min/max/gcd, range assign, lazy propagation, or persistence.
• Prefix Sum Patterns — static (no-update) range queries in O(1).
• Tree Patterns §2 — tin/tout flattening turns a subtree into a contiguous range, which is what makes subtree-sum-with-point-update a BIT problem.
• Binary Search — contrast with §7: the k-th descent walks the BIT’s own bit structure instead of wrapping a query in a search loop.
• Pattern Decision Map — the router: which technique does a cold problem call for?
• Pattern Mastery Program — the spaced-repetition schedule, mastery checklist, and drill formats that turn reading into recall.

Pattern mastered — two lines (i += i & -i to climb, i -= i & -i to descend) plus one question: am I indexing by position or by value?