vault

Fenwick Tree

17 min read

Fenwick Tree

A Fenwick tree (also called a Binary Indexed Tree, abbreviated BIT) is a compact data structure that supports two operations on an array A[1..n] of invertible aggregates (most commonly: sums) in O(log n) each: point update (A[i] += delta) and prefix-sum query (sum(A[1..i])). A range query sum(A[l..r]) follows from two prefix queries: prefix(r) − prefix(l - 1). The structure was published by Peter Fenwick in 1994 in Software: Practice and Experience — the original motivation was building cumulative-frequency tables for arithmetic coding compression — and the entire data structure rests on one bit-manipulation trick: i & -i extracts the lowest set bit of i. Compared to a Segment Tree, a Fenwick tree uses half the memory (n slots vs 4n), is dramatically simpler to code (a couple of while loops, no recursion), but supports a strictly narrower class of operations: only invertible aggregates (sum, XOR), only prefix-style queries (no general range-min/max). When your problem fits, Fenwick is the right hammer; when it doesn’t, fall back to Segment Tree.

1. Intuition — A Hierarchy of Cumulative Buckets

Imagine you’re tracking a running total of donations to a charity, indexed by donor ID 1..n. You want fast “total donated by donors 1..i” answers, and you also want to be able to update a single donor’s donation cheaply.

Strategy A: maintain the array directly. Update is O(1) (just write to A[i]). But prefix(i) requires summing A[1] + A[2] + … + A[i] = O(i) = O(n) worst case.

Strategy B: maintain prefix sums directly (P[i] = A[1] + … + A[i]). Now prefix(i) = P[i] is O(1). But updating A[i] requires updating every P[j] for j ≥ i — O(n) worst case.

Both strategies are dominated, in different directions, by O(n). The Fenwick tree is the balanced compromise: every operation O(log n). The structural idea is to not store all n prefix sums, and not store the raw array, but to store a clever subset of partial sums such that any prefix can be reconstructed by summing O(log n) of them, and any single update touches O(log n) of them.

The “clever subset” is: each BIT[i] stores a sum over a range whose length equals the lowest set bit of i. Specifically:

BIT[i] = A[i − lowbit(i) + 1] + A[i − lowbit(i) + 2] + … + A[i]

where lowbit(i) = i & -i (more on this in §3). For example with n = 8:

i (decimal)i (binary)lowbit(i)range covered by BIT[i]
100011A[1]
200102A[1..2]
300111A[3]
401004A[1..4]
501011A[5]
601102A[5..6]
701111A[7]
810008A[1..8]

Index 4 covers the four elements ending at position 4 (i.e., A[1..4]); index 2 covers A[1..2]; index 8 covers all eight. Index 5 only covers A[5] because lowbit(5) = 1. The lengths form a perfect “binary forest” — see §8.

To compute prefix(7): walk down 7 → 6 → 4 → 0. That’s BIT[7] + BIT[6] + BIT[4] = A[7] + A[5..6] + A[1..4] = A[1..7]. ✓ Three lookups for n = 8; in general, O(log n).

To update A[5] += δ: walk up 5 → 6 → 8 → .... Add δ to BIT[5], BIT[6], BIT[8]. Three updates for n = 8; in general, O(log n).

The walk-down step replaces i with i - lowbit(i). The walk-up step replaces i with i + lowbit(i). That is the entire data structure.

2. Tiny Worked Example

Let A = [3, 2, −1, 6, 5, 4, −3, 3] (1-indexed; A[1] = 3, …, A[8] = 3).

Build the BIT. A naive build calls update(i, A[i]) for each i, costing O(n log n). A linear-time build (Θ(n)) initializes BIT[i] = A[i], then for each i in increasing order pushes BIT[i]’s value up to its “parent” i + lowbit(i) if that’s ≤ n. Either way:

BIT[1] = A[1]                               =  3
BIT[2] = A[1] + A[2]                        =  5
BIT[3] = A[3]                               = -1
BIT[4] = A[1] + A[2] + A[3] + A[4]          = 10
BIT[5] = A[5]                               =  5
BIT[6] = A[5] + A[6]                        =  9
BIT[7] = A[7]                               = -3
BIT[8] = A[1] + … + A[8]                    = 19

Query prefix(6). Walk: 6 → 6 - lowbit(6) = 6 - 2 = 4 → 4 - lowbit(4) = 4 - 4 = 0. Stop. Sum: BIT[6] + BIT[4] = 9 + 10 = 19. Manual: 3 + 2 + (-1) + 6 + 5 + 4 = 19. ✓

Query prefix(7). Walk: 7 → 7 - 1 = 6 → 6 - 2 = 4 → 4 - 4 = 0. Sum: BIT[7] + BIT[6] + BIT[4] = -3 + 9 + 10 = 16. Manual: 3 + 2 - 1 + 6 + 5 + 4 - 3 = 16. ✓

Range query sum(A[3..6]). Compute prefix(6) - prefix(2) = 19 - (BIT[2]) = 19 - 5 = 14. Manual: -1 + 6 + 5 + 4 = 14. ✓

Update A[3] += 10 (so A[3] becomes 9). Walk up: 3 → 3 + lowbit(3) = 3 + 1 = 4 → 4 + 4 = 8 → 8 + 8 = 16 > n, stop. Add 10 to BIT[3], BIT[4], BIT[8]:

BIT[3] = -1 + 10 =  9
BIT[4] = 10 + 10 = 20
BIT[8] = 19 + 10 = 29

Re-query prefix(7): BIT[7] + BIT[6] + BIT[4] = -3 + 9 + 20 = 26. Manual: 3 + 2 + 9 + 6 + 5 + 4 - 3 = 26. ✓

The walk in both directions touches at most ⌊log₂ n⌋ + 1 indices.

3. The i & -i Bit Trick — Symbol-by-Symbol

This is the move that makes the whole structure work. We use two’s-complement integer representation throughout (all modern hardware).

Claim. For any positive integer i, the expression i & -i (bitwise AND of i with its arithmetic negation) returns an integer whose binary representation has a single 1 bit, located at the position of the lowest set bit of i (equivalently, the largest power of 2 that divides i).

Why. In two’s complement, -i = (~i) + 1 — flip all the bits, then add 1. Walk through what happens:

  • Flipping ~i turns every 0 of i into 1 and vice versa.
  • Adding 1 to ~i then propagates a carry from the lowest bit. The carry ripples through any trailing 1s in ~i (which were trailing 0s in i), turning them back to 0, and finally lands at the first 0 in ~i from the right, which is the first 1 in i from the right — i.e., the lowest set bit of i. After the add, the lowest set bit of i is now a 1 in -i; everything below it is 0 (because it was 0 in i, became 1 in ~i, then got carried-over back to 0). Everything above the lowest set bit of i is unchanged in absolute terms — ~i flipped them, and the carry didn’t reach that high; but we’re looking at ~i + 1, so the high bits of -i are exactly the bit-flipped high bits of i.

So, denoting the lowest set bit of i at position k:

  • Bits below k in i: 0s; in -i: 0s. AND: 0.
  • Bit at k in i: 1; in -i: 1. AND: 1.
  • Bits above k in i: arbitrary; in -i: bit-flipped. AND of a bit with its flip: 0.

Therefore i & -i has exactly one 1, at position k. ∎

Concrete examples.

i (decimal)i (8-bit binary)~i~i + 1 = -ii & -ilowbit
1000000011111111011111111000000011
2000000101111110111111110000000102
3000000111111110011111101000000011
4000001001111101111111100000001004
5000001011111101011111011000000011
6000001101111100111111010000000102
8000010001111011111111000000010008
12000011001111001111110100000011004

So lowbit(12) = 4, meaning a Fenwick index of 12 covers a range of length 4 ending at index 12, i.e., A[9..12].

Why the trick matters.

  • Walk-up (update): i ← i + lowbit(i) jumps to the “parent” Fenwick index — the next ancestor whose range covers A[i].
  • Walk-down (prefix query): i ← i - lowbit(i) strips the lowest set bit, jumping to the previous “sibling” range to be summed.
  • Both walks halve a meaningful quantity each step (the number of set bits between i and the boundary), so they terminate in O(log n) iterations.

In Python the & and unary minus work on arbitrary integers; in C/C++ on int you get the same behavior because int is two’s complement. In a language without two’s-complement (rare) you’d write i & (i ^ (i - 1)) instead.

4. Pseudocode

By convention Fenwick trees are 1-indexed — the math breaks at i = 0 because lowbit(0) = 0 and 0 + 0 is a fixed point. The internal array has size n + 1 and slot 0 is unused.

update(i, delta):              # A[i] += delta
    while i <= n:
        BIT[i] += delta
        i += i & -i            # walk up

prefix(i):                     # returns sum(A[1..i])
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i            # walk down
    return s

range_sum(l, r):
    return prefix(r) - prefix(l - 1)

build_linear(A):
    BIT[1..n] = A[1..n]
    for i = 1 to n:
        j = i + (i & -i)
        if j <= n:
            BIT[j] += BIT[i]

The linear build is Θ(n) because each index pushes its accumulated value to exactly one parent; total work is n pushes.

5. Python Implementation

A clean class-based Fenwick tree:

class FenwickTree:
    """1-indexed Fenwick tree (a.k.a. Binary Indexed Tree)
    supporting point-update and prefix-sum query in O(log n)."""
 
    def __init__(self, n_or_data):
        if isinstance(n_or_data, int):
            self.n = n_or_data
            self.bit = [0] * (self.n + 1)        # index 0 unused
        else:
            data = n_or_data
            self.n = len(data)
            self.bit = [0] + list(data)          # copy into 1-indexed slots
            for i in range(1, self.n + 1):       # linear build
                j = i + (i & -i)
                if j <= self.n:
                    self.bit[j] += self.bit[i]
 
    def update(self, i, delta):
        """Add `delta` to A[i].  1-indexed."""
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i
 
    def prefix(self, i):
        """Return sum(A[1..i]).  1-indexed; prefix(0) = 0."""
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
 
    def range_sum(self, l, r):
        """Return sum(A[l..r]).  1-indexed, inclusive."""
        return self.prefix(r) - self.prefix(l - 1)

Usage matching §2:

A = [3, 2, -1, 6, 5, 4, -3, 3]
ft = FenwickTree(A)
ft.prefix(6)        # → 19
ft.prefix(7)        # → 16
ft.range_sum(3, 6)  # → 14
ft.update(3, 10)    # A[3] += 10
ft.prefix(7)        # → 26

If your problem is naturally 0-indexed (e.g., LeetCode), wrap the public methods to add +1 to incoming indices — don’t try to make the BIT itself 0-indexed; the i & -i trick depends on i ≥ 1.

6. Complexity

Time.

  • update: Θ(log n). Proof: i + (i & -i) strictly increases i and at least doubles its lowest-set-bit position; after at most ⌊log₂ n⌋ + 1 iterations, i exceeds n and the loop halts.
  • prefix: Θ(log n). Proof: i - (i & -i) strictly decreases i by stripping its lowest set bit. The number of set bits in i is at most ⌊log₂ n⌋ + 1, so the loop runs that many times.
  • range_sum: Θ(log n). Two prefix calls.
  • build_linear: Θ(n). Each index does O(1) push.

Space. Θ(n). One array of n + 1 slots, vs 4n for Segment Tree. Roughly half the memory in practice.

7. Variants and Use Cases

7.1 Range Update + Point Query (via difference array)

Define D as the difference array of A: D[i] = A[i] - A[i-1]. Then A[i] = D[1] + D[2] + … + D[i] = prefix_D(i). A range update A[l..r] += k corresponds to two point updates on D: D[l] += k and D[r+1] -= k. So a Fenwick tree built over D supports range-add updates and point-queries in O(log n) each — and uses only one BIT, half the work of a Segment Tree with Lazy Propagation for the same operation pair.

7.2 Range Update + Range Query (two BITs)

A clever extension by Mishra & Sahni (folklore in CP) supports range-add + range-sum in O(log n) with two Fenwick trees, by maintaining the “linear part” and “constant part” of the running sum separately. The math: if you’ve performed range-adds on [l₁, r₁], [l₂, r₂], … with deltas k_j, then prefix(i) = Σ k_j × (i - l_j + 1) for the segments fully covering up to i, plus partial contributions. Reformulating: prefix(i) = i × Σ k_j - Σ k_j × (l_j - 1). Maintain two BITs — one for Σ k_j and one for Σ k_j × (l_j - 1) — and you can answer prefix(i) in O(log n). Implementation is short but tricky; cp-algorithms has a clean writeup.

7.3 2-D Fenwick Tree

A BIT of BITs. BIT2D[i][j] indexes a 2-D rectangle [1..i] × [1..j]. Update and query both cost O(log n × log m). Memory is O(nm). Used for 2-D range-sum problems with point updates (LC 308 Range Sum Query 2D — Mutable in O(n m + q log n log m) instead of segment-tree-of-segment-trees’ O(n m + q log² n)).

7.4 BIT for min / max — NO

This is one of the most-asked Stack-Overflow questions about BITs and the answer is you can’t, in general. Sum is invertible: prefix(r) - prefix(l - 1) = sum(A[l..r]). Min and max are not — there’s no way to recover min(A[l..r]) from min(A[1..r]) and min(A[1..l-1]). You can do “prefix-min queries” with a BIT (just replace += with min), but only if the only update operation is “set A[i] to a value smaller than its current value” — once decreases-only is broken, the structure breaks. Use a Segment Tree for general range-min/max with point updates.

7.5 BIT for XOR

XOR is its own inverse (a XOR a = 0), so a Fenwick tree storing XOR aggregates supports range_xor(l, r) = prefix_xor(r) XOR prefix_xor(l - 1) cleanly.

7.6 Order-Statistic BIT (find-the-k-th)

If A[i] is a frequency count of value i (0 or 1 in the simplest case), a BIT can answer “find the smallest index j such that prefix(j) ≥ k” — i.e., the k-th order statistic — in O(log n) using a top-down walk. This is the binary lifting on a BIT trick; foundational for LC 315 Count of Smaller Numbers After Self, LC 493 Reverse Pairs, and the offline/online algorithms for “median of a stream” with bounded values.

7.7 Production

BITs occasionally appear in production code where:

  • A small fixed-size table needs O(log n) cumulative-frequency updates (e.g., adaptive arithmetic coders — Fenwick’s original use case).
  • A column store maintains running totals under occasional updates (Apache Druid has historically used a BIT-like structure for some aggregator chains).
  • Real-time analytics dashboards over very small dimensions.

For larger production workloads, the LSM tree, B-tree, and skiplist dominate.

8. Pitfalls

  1. Off-by-one from forgetting 1-indexing. Fenwick is 1-indexed in the math. If your input array is 0-indexed (Python, LeetCode), wrap or shift indices on entry. A common bug: calling prefix(0) and getting 0 correctly, then accidentally querying prefix(-1) from a translated input — infinite loop because i > 0 never becomes false from a negative.
  2. Using a BIT for non-invertible aggregates. As covered in §7.4. If your problem requires range-min/max with arbitrary updates, BIT silently produces wrong answers. Use a Segment Tree.
  3. Forgetting that range query needs prefix(l - 1), not prefix(l). prefix(r) - prefix(l - 1) covers A[l..r] inclusive. Off-by-one bugs in this subtraction are easy.
  4. Misimplementing lowbit. In some languages or with unsigned int, -i doesn’t work as expected. In C, applying unary - to an unsigned produces a defined wraparound result that also gives the right bit pattern, but using i & (~i + 1) is more portable.
  5. Initializing with the slow n-update build. The naive build calls update for every element — O(n log n). The linear-time build (§4) is O(n) and worth using when n is large. Some contest solutions get TLE specifically because the build was O(n log n).
  6. Mixing 0-indexed array and 1-indexed BIT. If you manage both, document which is which — it is very easy to update the wrong index by 1 and end up with a BIT that’s correct almost everywhere.
  7. Trying to do “set A[i] = v” instead of “A[i] += delta”. BIT primitives are additive. To set A[i] = v, you compute delta = v - current_A_at_i and call update(i, delta). To get the current value, query range_sum(i, i). This is O(log n) rather than O(1), but unavoidable.
  8. Recursion not used — but the iterative loop has a subtle infinite-loop trap. If i is 0 and you write i -= i & -i, you get 0 - 0 = 0. Always guard with while i > 0. Symmetrically, in update, never call with i = 0.

9. Diagram

flowchart TD
    BIT8["BIT[8] : A[1..8]"]
    BIT4["BIT[4] : A[1..4]"]
    BIT2["BIT[2] : A[1..2]"]
    BIT1["BIT[1] : A[1]"]
    BIT3["BIT[3] : A[3]"]
    BIT6["BIT[6] : A[5..6]"]
    BIT5["BIT[5] : A[5]"]
    BIT7["BIT[7] : A[7]"]
    BIT8 --> BIT4
    BIT8 --> BIT6
    BIT8 --> BIT7
    BIT4 --> BIT2
    BIT4 --> BIT3
    BIT2 --> BIT1
    BIT6 --> BIT5

What this diagram shows. This is the implicit “Fenwick forest” for n = 8. Each node is a Fenwick array slot, labeled with the array range it summarizes. Edges go parent → child, where “parent” is i and “children” are the indices j such that j + lowbit(j) = i and j < i. Equivalently, the children of i are the indices reachable by stripping bits in the prefix-query walk: the descendants of BIT[i] are exactly the slots a prefix(i) walk would touch on its way down. The structure is not a single tree — it’s a forest of O(log n) trees rooted at the powers of 2; the “missing root” connecting BIT[8] to no parent simply means 8 + lowbit(8) = 16 > n and the walk-up stops. The depth of the deepest tree is ⌊log₂ n⌋ + 1, which gives the O(log n) operation bound. Notice that BIT[5], BIT[6] form their own little subtree — 5’s parent is 6, 6’s parent is 8 — and that BIT[7] sits alone with no children because no j < 7 has j + lowbit(j) = 7 (you can verify: j = 6 ⇒ 6 + 2 = 8 ≠ 7; no such j exists).

10. Common Interview Problems

LC #ProblemWhy Fenwick
307Range Sum Query — MutableCanonical point-update + prefix-sum
308Range Sum Query 2D — Mutable2-D Fenwick tree
315Count of Smaller Numbers After SelfCoordinate-compressed Fenwick + count queries
327Count of Range SumFenwick on cumulative-sum-rank-compressed array
493Reverse PairsSame idea as 315 with a different comparison
1395Count Number of TeamsFenwick over rank-compressed ratings
2179Count Good Triplets in an ArrayTwo Fenwicks counting “left less” and “right greater”
1409Queries on a Permutation With KeyOrder-statistic Fenwick
2031Count Subarrays With More Ones Than ZerosFenwick for prefix-sum frequencies
1505Minimum Possible Integer After at Most K Adjacent SwapsFenwick of “how many original positions are still unused before me”

A useful interview heuristic: when the problem screams “count inversions / count pairs with property P / k-th smallest dynamically”, a Fenwick tree (often after coordinate compression) is the cleanest tool.

11. Open Questions

  • How much of the practical advantage of Fenwick over Segment Tree is the constant factor (cache locality of one tight array vs. recursion overhead) versus the lower memory? Microbenchmarks vary; cp-algorithms claims ~2x in CP-style workloads.
  • Can you “lazy-propagate” range updates in a Fenwick tree without the two-BIT trick? The literature says no for general aggregates; the two-BIT decomposition is currently the best known for sum.
  • Is there a known information-theoretic argument that an O(log n)-per-op data structure cannot do better than ~n words of memory for cumulative frequencies? Fenwick uses exactly n; the question is whether n - O(log n) is achievable. (To my knowledge: no — but I haven’t found a tight bound in the literature.)

12. See Also

Graph View

Backlinks