Fenwick Tree Structure & lowbit

March 2026 · 18 min read

Before writing any code, let's deeply understand the structure that makes Fenwick trees tick. Every index in the BIT array stores a partial sum whose length is determined by a single bit operation. This post makes that fully concrete.

Why 1-Indexed?

Everything a Fenwick tree does is driven by the binary digits of an index, so the very first thing to pin down is where counting starts. Fenwick trees use 1-based indexing. The BIT array has size n + 1, and BIT[0] is unused (always 0). This is not just a convention, it's essential. The lowbit operation depends on the binary representation of the index, and lowbit(0) = 0 would cause an infinite loop.

// BIT array: indices 0..n, where BIT[0] = 0 (unused)
int BIT[n + 1];  // all zeros initially

The lowbit Function

Now that indices start at 1, we need a way to read their binary structure. That single job belongs to lowbit. The lowbit(i) function returns the value of the lowest set bit of i:

int lowbit(int i) {
    return i & (-i);
}

Why this works: in two's complement, -i equals ~i + 1. Flipping every bit and adding one leaves all the bits above the lowest 1 inverted, while the lowest 1 itself (and the zeros below it) end up matching i again. AND-ing the two together keeps only that one shared bit, the lowest 1.

Let’s trace through every index from 1 to 16:

Pattern: lowbit(i) isolates the last power of two present in i. The table hints at the covered range; now let's derive why that range is forced.

Why These Ranges? (Binary Decomposition)

Every positive integer has a unique binary expansion. Write i = 2a1 + 2a2 + ... + 2ak with a1 > a2 > ... > ak ≥ 0. The smallest power, 2ak, is exactly lowbit(i): the lowest 1-bit.

That expansion also chops the prefix [1..i] into contiguous power-of-two blocks. Read from left to right, the block sizes are 2a1, 2a2, ..., 2ak, and the final block ends exactly at i.

For i = 11, we have 11 = 10112 = 8 + 2 + 1. So the prefix [1..11] splits as [1..8] | [9..10] | [11..11]. The block sizes are 8, 2, 1; they add up to 11, they do not overlap, and together they cover the whole prefix.

prefix(7) works the same way: 7 = 1112 = 4 + 2 + 1, so [1..7] = [1..4] | [5..6] | [7..7].

The partition is unique because the last block is forced. Once a prefix ends at i, its rightmost block must have length lowbit(i). Remove that block and the same argument applies to the shorter prefix ending at i - lowbit(i). Peeling lowbits from right to left is not a trick; it is the only partition consistent with the binary expansion.

So the rightmost block always has length lowbit(i) and ends at i. That means BIT[i] stores the sum over [i - lowbit(i) + 1, i]. The “ends at i” part is not arbitrary; it drops straight out of the binary decomposition.

Update & Query Walks

We now know what each cell stores: a block ending at i of length lowbit(i). The two operations are just two ways of walking these blocks, and a single lowbit step is the only move we ever make.

Update: climb with i + lowbit(i)

To add a value at position i, we must fix every cell whose stored block contains i, because each of those cells holds a sum that i contributes to. The only question is which cells those are.

Start at BIT[i] itself: its block ends at i, so it certainly contains i. The next cell up that also contains i always sits at index i + lowbit(i). Here is why. A cell at index j covers [j - lowbit(j) + 1, j], so to still reach back to i it has to start at or before i. Adding lowbit(i) erases i's lowest set bit and carries it one place left, giving the nearest larger index whose block is wide enough to stretch back over i. Every index strictly between i and i + lowbit(i) either ends before i or starts after it, so none of them qualify.

We repeat the jump, each time landing on the next-higher cell that still covers i, until the index runs off the end of the array. Take an update at position 5 in an array of size 8:

Update walk at i = 5 (add lowbit):
  5                  → BIT[5] covers [5,5]   contains 5
  5 + lowbit(5) = 6  → BIT[6] covers [5,6]   contains 5
  6 + lowbit(6) = 8  → BIT[8] covers [1,8]   contains 5
  8 + lowbit(8) = 16 → past n = 8, stop

So adding to position 5 touches exactly three cells: BIT[5], BIT[6], and BIT[8]. Those are the only blocks that include index 5, which means those are the only stored sums that change.

Query: descend with i - lowbit(i)

A prefix sum sum(1..i) is the mirror walk. Cell i already holds the block ending at i, so add it first. Subtracting lowbit(i) drops to the cell holding the block immediately to its left; add that, and repeat until the index reaches 0. You are simply collecting the contiguous power-of-two blocks the prefix splits into, the same partition we derived above.

Query walk for sum(1..7) (strip lowbit):
  7                  → BIT[7] covers [7,7]
  7 - lowbit(7) = 6  → BIT[6] covers [5,6]
  6 - lowbit(6) = 4  → BIT[4] covers [1,4]
  4 - lowbit(4) = 0  → stop

Adding BIT[7] + BIT[6] + BIT[4] sums the blocks [7,7] | [5,6] | [1,4], which is exactly [1..7] with no gaps and no overlap.

Each jump clears one set bit from the index, and an index has at most log₂ n set bits. So both walks touch at most O(log n) cells, and that is where the speed comes from.

Building the BIT in O(n)

Those parent links aren't just theory; they hand us a fast way to fill the array. The naive way to build a BIT is to call update(i, arr[i]) for each element, that's O(n log n). But there's a clever O(n) approach:

void build(int arr[], int n) {
    // Copy values: BIT[i] = arr[i-1] (1-indexed)
    for (int i = 1; i <= n; i++)
        BIT[i] = arr[i - 1];
    
    // Propagate: each index adds its value to its parent
    for (int i = 1; i <= n; i++) {
        int parent = i + (i & (-i));
        if (parent <= n)
            BIT[parent] += BIT[i];
    }
}

Why this works: After copying, BIT[i] only has its own element's value. The second loop makes each node propagate its accumulated partial sum to its immediate parent. Because we iterate from left to right, by the time we process index i, all indices < i that feed into i have already propagated. And we only propagate to the immediate parent (one hop), not all ancestors, the chain effect handles the rest.

Trace for arr = [3, 2, -1, 6, 5, 4, -3, 3]

Why It Forms a Tree

We've been saying “parent” all along, so here's why the structure is genuinely a tree and not just a metaphor. Every index i (except the largest power of 2) has exactly one update-parent: i + lowbit(i). A parent can have several children, but each node has only one way to move upward. That one-outgoing-edge rule is what makes the structure a forest of trees (or a single tree if n is a power of 2).

For n = 8:

         8
       / | \
      4  6  7
    / |  |
   2  3  5
   |
   1

Node 8 is the root (it covers the entire array). Node 4 covers [1,4] and is a child of 8. Node 2 covers [1,2] and is a child of 4. And so on.

This tree has O(log n) depth, which is why both queries and updates take O(log n) time.

Memory Layout

Ranges, parents, the whole tree: all of it lives in one place. One of the best things about Fenwick trees is that the entire structure is a single array. No pointers, no nodes, no extra bookkeeping:

// That's it. The entire data structure.
int BIT[n + 1] = {0};  // index 0 unused

Compare with a segment tree, which needs 4n space for the tree array plus potential recursion stack overhead. The BIT uses n + 1 integers, less than half the memory. This also means better cache locality since both query and update access a small number of nearby indices.

Summary

• lowbit(i) = i & (-i) gives the lowest set bit, which determines how many elements index i is responsible for.
• Index i stores the sum of elements in range [i - lowbit(i) + 1, i].
• Update-parent: i + lowbit(i). Query-predecessor: i - lowbit(i).
• The BIT can be built in O(n) with a single forward pass.
• The implicit tree has O(log n) depth, so both queries and updates are O(log n).