Data Structures & AlgorithmsFenwick Trees (Binary Indexed Trees)

Fenwick Trees — Binary Indexed Trees

LevelAdvanced

Duration90 mins

TopicFenwick Trees (Binary Indexed Trees)

2 / 5

BIT Structure and Representation

The Elegant Mathematics Behind BITs

In the previous page, you saw the remarkably simple code for Fenwick Trees — just two small loops using the mysterious expression i & (-i). But why does this work? How can such simple operations maintain a data structure that answers prefix queries in O(log n) time?

The answer lies in a beautiful exploitation of binary representation. Every index i in the BIT is responsible for storing a partial sum of a specific range of elements, and this range is determined entirely by the binary structure of i itself.

This page will reveal the elegant mathematics behind Fenwick Trees, transforming them from magical incantations into deeply understood tools.

What You Will Learn

By the end of this page, you will understand: • How binary representation determines each index's responsibility • The meaning and mechanics of the lowest set bit (LSB) • How i & (-i) extracts the LSB using two's complement • The complete structure of a Fenwick Tree visualized • Why the tree has exactly O(log n) levels • The relationship between BIT indices and the ranges they represent

The Core Insight — Binary Representation

To understand Fenwick Trees, we must first appreciate a key observation about binary numbers and their relationship to range decomposition.

The observation:

Every positive integer can be uniquely expressed as a sum of distinct powers of 2 (its binary representation). For example:

13 = 8 + 4 + 1 = 2³ + 2² + 2⁰ = 1101₂
7 = 4 + 2 + 1 = 2² + 2¹ + 2⁰ = 0111₂
12 = 8 + 4 = 2³ + 2² = 1100₂

Fenwick's insight:

We can decompose the prefix sum query for index i into at most log₂(i) partial sums, where each partial sum covers a range whose length is a power of 2.

For the prefix [1..13], we can compute:

Sum of [1..8] (length 8 = 2³)
Plus sum of [9..12] (length 4 = 2²)
Plus sum of [13..13] (length 1 = 2⁰)

This decomposition follows directly from the binary representation of 13 = 1101₂. The set bits tell us which power-of-2-sized ranges to include!

Binary Decomposition Examples
Decimal	Binary	Decomposition	Prefix Parts
7	0111	4 + 2 + 1	[1..4] + [5..6] + [7..7]
10	1010	8 + 2	[1..8] + [9..10]
12	1100	8 + 4	[1..8] + [9..12]
15	1111	8 + 4 + 2 + 1	[1..8] + [9..12] + [13..14] + [15..15]
16	10000	16	[1..16]

The Key Pattern

The number of set bits in i (popcount) determines exactly how many partial sums we need for prefix[1..i]. Since any n-bit number has at most n set bits, and n = O(log i), we get O(log n) operations per query!

The Lowest Set Bit — The Heart of BITs

The lowest set bit (LSB) of a number is the rightmost bit that is 1 in its binary representation. This single concept is the key to understanding Fenwick Trees.

Definition:

For any positive integer i, the LSB (also called the "lowbit") is:

The largest power of 2 that divides i
The value of the rightmost 1-bit
The length of the range that index i is responsible for in the BIT

Examples:

Lowest Set Bit Examples
Decimal i	Binary	LSB Position	LSB Value	Range Length
1	0001	0	1 (2⁰)	1
2	0010	1	2 (2¹)	2
3	0011	0	1 (2⁰)	1
4	0100	2	4 (2²)	4
5	0101	0	1 (2⁰)	1
6	0110	1	2 (2¹)	2
7	0111	0	1 (2⁰)	1
8	1000	3	8 (2³)	8
12	1100	2	4 (2²)	4

Pattern recognition:

Notice the patterns:

All odd numbers have LSB = 1 (responsible for single elements)
Numbers divisible by 2 but not 4 have LSB = 2 (responsible for 2 elements)
Numbers divisible by 4 but not 8 have LSB = 4 (responsible for 4 elements)
And so on...

The fundamental rule:

Index i in a Fenwick Tree stores the sum of the LSB(i) elements ending at position i.

This means:

BIT[1] stores A[1] alone (LSB = 1)
BIT[2] stores A[1] + A[2] (LSB = 2, range of 2 ending at 2)
BIT[4] stores A[1] + A[2] + A[3] + A[4] (LSB = 4, range of 4 ending at 4)
BIT[6] stores A[5] + A[6] (LSB = 2, range of 2 ending at 6)
BIT[8] stores A[1] + ... + A[8] (LSB = 8, range of 8 ending at 8)

Extracting the LSB — The i & (-i) Trick

How do we efficiently extract the lowest set bit? The answer uses a beautiful property of two's complement representation of negative numbers.

Two's Complement Review:

In two's complement (the standard way computers represent signed integers):

To negate a number, flip all bits and add 1
Or equivalently: -x = ~x + 1

The Magic:

For any integer i, the expression i & (-i) gives exactly the lowest set bit value!

Why does this work?

Let's trace through with i = 12:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
i = 12
Binary representation: 01100
 
To find -i, we:
1. Flip all bits:    10011
2. Add 1:            10100
 
Now compute i & (-i):
   01100  (12)
 & 10100  (-12)
   -----
   00100  (4)
 
The result is 4, which is exactly the LSB of 12!
 
Why it works:
- Consider i = ...xyz100...0 (generic form with trailing zeros)
- The rightmost 1 is followed by all zeros
- When we flip bits: ...XYZ011...1 (xyz become XYZ, 100...0 becomes 011...1)
- Add 1: ...XYZ100...0 (carry propagates through 1s, flips back to 100...0)
- AND: the only position where both have 1 is the original LSB position!

Alternative Notation

You'll often see the LSB extraction written as: • lowbit(i) = i & (-i) • LSB(i) = i & (-i) • i & -i (without parentheses) All mean the same thing. Some implementations define a helper function for clarity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Multiple ways to express the same operation
function getLSB(i: number): number {
    return i & (-i);
}
 
// Examples
console.log(getLSB(1));   // 1 (binary: 0001 → LSB = 0001 = 1)
console.log(getLSB(6));   // 2 (binary: 0110 → LSB = 0010 = 2)
console.log(getLSB(8));   // 8 (binary: 1000 → LSB = 1000 = 8)
console.log(getLSB(12));  // 4 (binary: 1100 → LSB = 0100 = 4)
console.log(getLSB(7));   // 1 (binary: 0111 → LSB = 0001 = 1)
 
// Verify: LSB(i) always equals the largest power of 2 dividing i
function verifyLSB(i: number): boolean {
    const lsb = i & (-i);
    return i % lsb === 0 && i % (lsb * 2) !== 0;
}
 
// Alternative implementation using only positive numbers
function getLSBAlt(i: number): number {
    return i & (~i + 1);  // Explicitly compute two's complement
}

The BIT Array — What Each Index Stores

Now we can precisely define what each index in the Fenwick Tree stores.

The Rule:

BIT[i] = sum of A[i - LSB(i) + 1] to A[i]

In other words, BIT[i] stores the sum of LSB(i) elements ending at position i.

Let's build a complete example for an 8-element array:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Original array A:  A[1]  A[2]  A[3]  A[4]  A[5]  A[6]  A[7]  A[8]
 
Index i  | Binary | LSB(i) | Range Start | Range End | BIT[i] stores
---------|--------|--------|-------------|-----------|------------------
   1     |  0001  |   1    |     1       |    1      | A[1]
   2     |  0010  |   2    |     1       |    2      | A[1] + A[2]
   3     |  0011  |   1    |     3       |    3      | A[3]
   4     |  0100  |   4    |     1       |    4      | A[1] + A[2] + A[3] + A[4]
   5     |  0101  |   1    |     5       |    5      | A[5]
   6     |  0110  |   2    |     5       |    6      | A[5] + A[6]
   7     |  0111  |   1    |     7       |    7      | A[7]
   8     |  1000  |   8    |     1       |    8      | A[1] + A[2] + ... + A[8]
 
Key insight: Range start = i - LSB(i) + 1
             Range end = i
             Range length = LSB(i)

Visualizing the coverage:

Each BIT[i] covers a contiguous range of the original array. These ranges have a beautiful nested structure:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Array positions:     1     2     3     4     5     6     7     8
                     ─────────────────────────────────────────────────
 
BIT[1]:             [─]                                           (covers 1)
BIT[2]:             [───────]                                     (covers 1-2)
BIT[3]:                     [─]                                   (covers 3)
BIT[4]:             [─────────────────]                           (covers 1-4)
BIT[5]:                                 [─]                       (covers 5)
BIT[6]:                                 [───────]                 (covers 5-6)
BIT[7]:                                         [─]               (covers 7)
BIT[8]:             [─────────────────────────────────────────]   (covers 1-8)
 
Notice the hierarchical structure:
- BIT[8] contains everything
- BIT[4] overlaps with BIT[1], BIT[2], BIT[3]
- BIT[6] overlaps with BIT[5]
- Odd indices always cover single elements

The Binary Pattern

The visual shows that indices with more trailing zeros in their binary representation cover larger ranges. Index 8 (1000₂) covers 8 elements, index 4 (100₂) covers 4 elements, index 2 (10₂) covers 2 elements, and all odd indices cover just 1 element.

The Tree Structure — Parent-Child Relationships

Although we call it a "tree," a Fenwick Tree is stored as a flat array. The tree structure exists implicitly through index relationships.

Parent-Child Relationship:

When we update a value, we need to update all indices whose ranges include that position. The parent of index i is:

parent(i) = i + LSB(i)

This gives us the next index that needs to be updated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
For n = 16, trace the parent chains:
 
Starting from 1:
1 → 1 + LSB(1) = 1 + 1 = 2
2 → 2 + LSB(2) = 2 + 2 = 4
4 → 4 + LSB(4) = 4 + 4 = 8
8 → 8 + LSB(8) = 8 + 8 = 16
16 → 16 + LSB(16) = 16 + 16 = 32 (beyond n, stop)
 
Path: 1 → 2 → 4 → 8 → 16
 
Starting from 3:
3 → 3 + LSB(3) = 3 + 1 = 4
4 → 4 + LSB(4) = 4 + 4 = 8
8 → 8 + LSB(8) = 8 + 8 = 16
 
Path: 3 → 4 → 8 → 16
 
Starting from 7:
7 → 7 + LSB(7) = 7 + 1 = 8
8 → 8 + LSB(8) = 8 + 8 = 16
 
Path: 7 → 8 → 16
 
Starting from 5:
5 → 5 + LSB(5) = 5 + 1 = 6
6 → 6 + LSB(6) = 6 + 2 = 8
8 → 8 + LSB(8) = 8 + 8 = 16
 
Path: 5 → 6 → 8 → 16

Visualizing as a tree:

The BIT can be visualized as a forest of trees rooted at powers of 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
                                16
                               / | \
                              /  |  \
                             8   12  14  15
                           / |\   |\   |
                          4 6 7  10 11 13
                         /| |    |
                        2 3 5    9
                        |
                        1
 
Each node stores the sum for its responsibility range:
- Node 16: sum of A[1..16]
- Node 8:  sum of A[1..8]
- Node 4:  sum of A[1..4]
- Node 12: sum of A[9..12]
- Node 6:  sum of A[5..6]
 
Update path: When updating A[i], follow i → parent(i) → parent(parent(i)) → ...
Query path:  Go in opposite direction (handled by subtracting LSB)

It's Not a Binary Tree!

Despite the name "Binary Indexed Tree," the implicit tree structure is NOT a binary tree. A node can have multiple children. The "binary" in the name refers to the use of binary representation of indices, not the tree's branching factor.

Query Path — Traversing for Prefix Sums

Now we can understand how queries work. To compute prefix sum from 1 to i, we:

Start at index i
Add BIT[i] to our sum
Move to i - LSB(i) (strip the lowest set bit)
Repeat until i becomes 0

Why this works:

Each step collects a disjoint portion of the prefix sum. The ranges don't overlap because each index covers elements ending at that index.

Example: Query prefix sum [1..13]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Query prefix sum from 1 to 13:
 
Step 1: i = 13 (binary: 1101)
        BIT[13] covers A[13..13] (LSB = 1)
        Add BIT[13] to sum
        i = 13 - 1 = 12
 
Step 2: i = 12 (binary: 1100)
        BIT[12] covers A[9..12] (LSB = 4)
        Add BIT[12] to sum
        i = 12 - 4 = 8
 
Step 3: i = 8 (binary: 1000)
        BIT[8] covers A[1..8] (LSB = 8)
        Add BIT[8] to sum
        i = 8 - 8 = 0
 
Step 4: i = 0, STOP
 
Total: BIT[13] + BIT[12] + BIT[8]
     = A[13] + (A[9]+A[10]+A[11]+A[12]) + (A[1]+...+A[8])
     = A[1] + A[2] + ... + A[13] ✓
 
Ranges collected: [13..13], [9..12], [1..8]
These are disjoint and cover [1..13] exactly!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class FenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    /**
     * Query prefix sum from index 1 to i
     * 
     * The loop processes each set bit of i exactly once.
     * Since i has at most log₂(n) bits, this is O(log n).
     */
    query(i: number): number {
        let sum = 0;
        
        while (i > 0) {
            // BIT[i] covers the range [i - LSB(i) + 1, i]
            // Add this partial sum to our total
            sum += this.tree[i];
            
            // Remove the LSB from i
            // This moves us to the previous disjoint range
            // i & (i - 1) also strips the LSB, but i -= i & (-i) is clearer
            i -= i & (-i);
        }
        
        return sum;
    }
 
    // Range query [l, r] derived from prefix queries
    rangeQuery(l: number, r: number): number {
        // prefix(r) - prefix(l-1) gives exactly [l, r]
        return this.query(r) - this.query(l - 1);
    }
}
 
// Trace the query for i = 13
// i = 13 (1101₂): sum += tree[13], i = 13 - 1 = 12
// i = 12 (1100₂): sum += tree[12], i = 12 - 4 = 8
// i = 8  (1000₂): sum += tree[8],  i = 8 - 8 = 0
// i = 0: loop ends
// Total iterations: 3 = popcount(13) = number of set bits in 13

Number of Iterations = popcount(i)

The query loop runs exactly popcount(i) times — once for each set bit in i. For any i ≤ n, this is at most log₂(n) iterations. In practice, the average is about log₂(n)/2 iterations since random numbers have about half their bits set.

The Mathematical Invariant

Let's formally state the invariant that makes Fenwick Trees work:

Invariant:

For any index i where 1 ≤ i ≤ n:

BIT[i] = Σ A[j] for all j in [i - LSB(i) + 1, i]

Equivalently:

BIT[i] = A[i - LSB(i) + 1] + A[i - LSB(i) + 2] + ... + A[i]

Corollary — Prefix Sum Formula:

prefix(i) = Σ BIT[k] where k traverses i → i - LSB(i) → ... → 0

The proof that this correctly computes prefix sums follows from:

Each BIT[k] in the traversal covers a disjoint range
The union of all traversed ranges equals exactly [1, i]
Therefore, the sum of BIT values equals the prefix sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * This function verifies that the BIT invariant holds.
 * For each index i, we check that BIT[i] equals the sum of the
 * expected range in the original array.
 */
function verifyBITInvariant(bit: number[], original: number[]): boolean {
    const n = original.length; // original is 1-indexed
    
    for (let i = 1; i <= n; i++) {
        const lsb = i & (-i);
        const rangeStart = i - lsb + 1;
        const rangeEnd = i;
        
        // Calculate expected sum for this range
        let expectedSum = 0;
        for (let j = rangeStart; j <= rangeEnd; j++) {
            expectedSum += original[j];
        }
        
        // Verify BIT[i] matches
        if (bit[i] !== expectedSum) {
            console.log(`Invariant violated at i=${i}`);
            console.log(`Expected: ${expectedSum}, Actual: ${bit[i]}`);
            return false;
        }
    }
    
    return true;
}
 
/**
 * This function verifies that prefix queries return correct results.
 */
function verifyPrefixQueries(bit: FenwickTree, original: number[]): boolean {
    const n = original.length - 1; // original is 1-indexed
    
    for (let i = 1; i <= n; i++) {
        // Calculate expected prefix sum
        let expected = 0;
        for (let j = 1; j <= i; j++) {
            expected += original[j];
        }
        
        const actual = bit.query(i);
        
        if (actual !== expected) {
            console.log(`Query mismatch at i=${i}`);
            console.log(`Expected: ${expected}, Actual: ${actual}`);
            return false;
        }
    }
    
    return true;
}

A Beautiful Decomposition

The query path for index i corresponds exactly to the binary representation of i. Each set bit contributes one range to the prefix sum. This is why Fenwick Trees are also called "Binary Indexed Trees" — the binary digits quite literally index into the tree structure!

Memory Layout — Why It's Efficient

One of the Fenwick Tree's advantages is its memory efficiency. Let's examine why:

Space Comparison:

Memory Usage Comparison
Data Structure	Space	For n = 1,000,000 (64-bit integers)
Original Array	n elements	8 MB
Fenwick Tree	n + 1 elements	~8 MB (plus 8 bytes)
Prefix Sum Array	n elements	8 MB (but no updates!)
Segment Tree (typical)	4n elements	~32 MB
Segment Tree (optimized)	2n elements	~16 MB

Cache Efficiency:

Beyond raw size, Fenwick Trees have excellent cache performance:

Contiguous memory: The BIT is a simple array with excellent spatial locality
Predictable access patterns: Both query and update traverse indices in a predictable manner
Fewer cache lines touched: A query or update touches at most log₂(n) elements, often in nearby memory locations
No pointer chasing: Unlike tree-based structures, there are no pointers to follow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Memory-efficient Fenwick Tree implementation
 * Uses exactly (n + 1) * sizeof(element) bytes
 */
class MemoryEfficientBIT {
    // Single contiguous array - excellent cache behavior
    private readonly tree: number[];
    private readonly n: number;
 
    constructor(n: number) {
        this.n = n;
        // Allocate exactly n+1 elements (index 0 unused)
        this.tree = new Array(n + 1).fill(0);
    }
 
    // Notice: query and update both access memory in predictable patterns
    // For i = 13, query accesses: tree[13], tree[12], tree[8]
    // These indices decrease, giving good spatial locality
 
    update(i: number, delta: number): void {
        // Indices increase: 13 → 14 → 16 → ...
        // Increasing access pattern is cache-friendly
        for (; i <= this.n; i += i & (-i)) {
            this.tree[i] += delta;
        }
    }
 
    query(i: number): number {
        let sum = 0;
        // Indices decrease: 13 → 12 → 8
        // Decreasing access pattern still has good locality
        for (; i > 0; i -= i & (-i)) {
            sum += this.tree[i];
        }
        return sum;
    }
 
    // Memory footprint analysis
    getMemoryUsage(): number {
        // Each element is a 64-bit number (8 bytes in most contexts)
        return (this.n + 1) * 8; // bytes
    }
}
 
// Compare memory footprint
const n = 1_000_000;
const bit = new MemoryEfficientBIT(n);
console.log(`BIT memory: ${bit.getMemoryUsage() / 1024 / 1024} MB`);
console.log(`Segment tree would use: ${(4 * n * 8) / 1024 / 1024} MB`);
// BIT: ~8 MB, Segment Tree: ~32 MB

Summary — The Binary Index Structure

This page revealed the elegant mathematics that power Fenwick Trees. Here are the key takeaways:

Key Takeaways

•Binary representation determines the structure: each index covers a range whose length equals its lowest set bit (LSB).
•LSB(i) = i & (-i) extracts the lowest set bit using two's complement arithmetic — the fundamental operation in BITs.
•BIT[i] stores the sum of elements from (i - LSB(i) + 1) to i, a range of exactly LSB(i) elements.
•Query traversal strips LSB repeatedly (i -= i & (-i)), visiting exactly popcount(i) indices, which is O(log n).
•Update traversal goes the opposite direction (i += i & (-i)), propagating changes to all covering indices.
•The tree structure is implicit — stored as a flat array with parent relationships encoded in binary representation.
•Memory efficiency is excellent: exactly n+1 elements with superb cache locality.

What's next:

Now that you understand the structure and representation of Fenwick Trees, we'll examine the query operation in depth. The next page covers prefix sum queries — how to efficiently compute cumulative sums using the BIT structure we've just explored.

Page Complete

You now have a deep understanding of Fenwick Tree structure — the binary indexing scheme, the responsibility ranges, and why the simple bit manipulation operations traverse the tree correctly. This foundation prepares you for implementing and reasoning about BIT operations with confidence.

2 / 5

Loading learning content...

Data Structures & AlgorithmsFenwick Trees (Binary Indexed Trees)

Fenwick Trees — Binary Indexed Trees

LevelAdvanced

Duration90 mins

TopicFenwick Trees (Binary Indexed Trees)

2 / 5

BIT Structure and Representation

The Elegant Mathematics Behind BITs

This page will reveal the elegant mathematics behind Fenwick Trees, transforming them from magical incantations into deeply understood tools.

What You Will Learn

The Core Insight — Binary Representation

To understand Fenwick Trees, we must first appreciate a key observation about binary numbers and their relationship to range decomposition.

The observation:

Every positive integer can be uniquely expressed as a sum of distinct powers of 2 (its binary representation). For example:

13 = 8 + 4 + 1 = 2³ + 2² + 2⁰ = 1101₂
7 = 4 + 2 + 1 = 2² + 2¹ + 2⁰ = 0111₂
12 = 8 + 4 = 2³ + 2² = 1100₂

Fenwick's insight:

We can decompose the prefix sum query for index i into at most log₂(i) partial sums, where each partial sum covers a range whose length is a power of 2.

For the prefix [1..13], we can compute:

Sum of [1..8] (length 8 = 2³)
Plus sum of [9..12] (length 4 = 2²)
Plus sum of [13..13] (length 1 = 2⁰)

This decomposition follows directly from the binary representation of 13 = 1101₂. The set bits tell us which power-of-2-sized ranges to include!

Binary Decomposition Examples
Decimal	Binary	Decomposition	Prefix Parts
7	0111	4 + 2 + 1	[1..4] + [5..6] + [7..7]
10	1010	8 + 2	[1..8] + [9..10]
12	1100	8 + 4	[1..8] + [9..12]
15	1111	8 + 4 + 2 + 1	[1..8] + [9..12] + [13..14] + [15..15]
16	10000	16	[1..16]

The Key Pattern

The Lowest Set Bit — The Heart of BITs

The lowest set bit (LSB) of a number is the rightmost bit that is 1 in its binary representation. This single concept is the key to understanding Fenwick Trees.

Definition:

For any positive integer i, the LSB (also called the "lowbit") is:

The largest power of 2 that divides i
The value of the rightmost 1-bit
The length of the range that index i is responsible for in the BIT

Examples:

Lowest Set Bit Examples
Decimal i	Binary	LSB Position	LSB Value	Range Length
1	0001	0	1 (2⁰)	1
2	0010	1	2 (2¹)	2
3	0011	0	1 (2⁰)	1
4	0100	2	4 (2²)	4
5	0101	0	1 (2⁰)	1
6	0110	1	2 (2¹)	2
7	0111	0	1 (2⁰)	1
8	1000	3	8 (2³)	8
12	1100	2	4 (2²)	4

Pattern recognition:

Notice the patterns:

All odd numbers have LSB = 1 (responsible for single elements)
Numbers divisible by 2 but not 4 have LSB = 2 (responsible for 2 elements)
Numbers divisible by 4 but not 8 have LSB = 4 (responsible for 4 elements)
And so on...

The fundamental rule:

Index i in a Fenwick Tree stores the sum of the LSB(i) elements ending at position i.

This means:

BIT[1] stores A[1] alone (LSB = 1)
BIT[2] stores A[1] + A[2] (LSB = 2, range of 2 ending at 2)
BIT[4] stores A[1] + A[2] + A[3] + A[4] (LSB = 4, range of 4 ending at 4)
BIT[6] stores A[5] + A[6] (LSB = 2, range of 2 ending at 6)
BIT[8] stores A[1] + ... + A[8] (LSB = 8, range of 8 ending at 8)

Extracting the LSB — The i & (-i) Trick

How do we efficiently extract the lowest set bit? The answer uses a beautiful property of two's complement representation of negative numbers.

Two's Complement Review:

In two's complement (the standard way computers represent signed integers):

To negate a number, flip all bits and add 1
Or equivalently: -x = ~x + 1

The Magic:

For any integer i, the expression i & (-i) gives exactly the lowest set bit value!

Why does this work?

Let's trace through with i = 12:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
i = 12
Binary representation: 01100
 
To find -i, we:
1. Flip all bits:    10011
2. Add 1:            10100
 
Now compute i & (-i):
   01100  (12)
 & 10100  (-12)
   -----
   00100  (4)
 
The result is 4, which is exactly the LSB of 12!
 
Why it works:
- Consider i = ...xyz100...0 (generic form with trailing zeros)
- The rightmost 1 is followed by all zeros
- When we flip bits: ...XYZ011...1 (xyz become XYZ, 100...0 becomes 011...1)
- Add 1: ...XYZ100...0 (carry propagates through 1s, flips back to 100...0)
- AND: the only position where both have 1 is the original LSB position!

Alternative Notation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Multiple ways to express the same operation
function getLSB(i: number): number {
    return i & (-i);
}
 
// Examples
console.log(getLSB(1));   // 1 (binary: 0001 → LSB = 0001 = 1)
console.log(getLSB(6));   // 2 (binary: 0110 → LSB = 0010 = 2)
console.log(getLSB(8));   // 8 (binary: 1000 → LSB = 1000 = 8)
console.log(getLSB(12));  // 4 (binary: 1100 → LSB = 0100 = 4)
console.log(getLSB(7));   // 1 (binary: 0111 → LSB = 0001 = 1)
 
// Verify: LSB(i) always equals the largest power of 2 dividing i
function verifyLSB(i: number): boolean {
    const lsb = i & (-i);
    return i % lsb === 0 && i % (lsb * 2) !== 0;
}
 
// Alternative implementation using only positive numbers
function getLSBAlt(i: number): number {
    return i & (~i + 1);  // Explicitly compute two's complement
}

The BIT Array — What Each Index Stores

Now we can precisely define what each index in the Fenwick Tree stores.

The Rule:

BIT[i] = sum of A[i - LSB(i) + 1] to A[i]

In other words, BIT[i] stores the sum of LSB(i) elements ending at position i.

Let's build a complete example for an 8-element array:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Original array A:  A[1]  A[2]  A[3]  A[4]  A[5]  A[6]  A[7]  A[8]
 
Index i  | Binary | LSB(i) | Range Start | Range End | BIT[i] stores
---------|--------|--------|-------------|-----------|------------------
   1     |  0001  |   1    |     1       |    1      | A[1]
   2     |  0010  |   2    |     1       |    2      | A[1] + A[2]
   3     |  0011  |   1    |     3       |    3      | A[3]
   4     |  0100  |   4    |     1       |    4      | A[1] + A[2] + A[3] + A[4]
   5     |  0101  |   1    |     5       |    5      | A[5]
   6     |  0110  |   2    |     5       |    6      | A[5] + A[6]
   7     |  0111  |   1    |     7       |    7      | A[7]
   8     |  1000  |   8    |     1       |    8      | A[1] + A[2] + ... + A[8]
 
Key insight: Range start = i - LSB(i) + 1
             Range end = i
             Range length = LSB(i)

Visualizing the coverage:

Each BIT[i] covers a contiguous range of the original array. These ranges have a beautiful nested structure:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Array positions:     1     2     3     4     5     6     7     8
                     ─────────────────────────────────────────────────
 
BIT[1]:             [─]                                           (covers 1)
BIT[2]:             [───────]                                     (covers 1-2)
BIT[3]:                     [─]                                   (covers 3)
BIT[4]:             [─────────────────]                           (covers 1-4)
BIT[5]:                                 [─]                       (covers 5)
BIT[6]:                                 [───────]                 (covers 5-6)
BIT[7]:                                         [─]               (covers 7)
BIT[8]:             [─────────────────────────────────────────]   (covers 1-8)
 
Notice the hierarchical structure:
- BIT[8] contains everything
- BIT[4] overlaps with BIT[1], BIT[2], BIT[3]
- BIT[6] overlaps with BIT[5]
- Odd indices always cover single elements

The Binary Pattern

The Tree Structure — Parent-Child Relationships

Although we call it a "tree," a Fenwick Tree is stored as a flat array. The tree structure exists implicitly through index relationships.

Parent-Child Relationship:

When we update a value, we need to update all indices whose ranges include that position. The parent of index i is:

parent(i) = i + LSB(i)

This gives us the next index that needs to be updated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
For n = 16, trace the parent chains:
 
Starting from 1:
1 → 1 + LSB(1) = 1 + 1 = 2
2 → 2 + LSB(2) = 2 + 2 = 4
4 → 4 + LSB(4) = 4 + 4 = 8
8 → 8 + LSB(8) = 8 + 8 = 16
16 → 16 + LSB(16) = 16 + 16 = 32 (beyond n, stop)
 
Path: 1 → 2 → 4 → 8 → 16
 
Starting from 3:
3 → 3 + LSB(3) = 3 + 1 = 4
4 → 4 + LSB(4) = 4 + 4 = 8
8 → 8 + LSB(8) = 8 + 8 = 16
 
Path: 3 → 4 → 8 → 16
 
Starting from 7:
7 → 7 + LSB(7) = 7 + 1 = 8
8 → 8 + LSB(8) = 8 + 8 = 16
 
Path: 7 → 8 → 16
 
Starting from 5:
5 → 5 + LSB(5) = 5 + 1 = 6
6 → 6 + LSB(6) = 6 + 2 = 8
8 → 8 + LSB(8) = 8 + 8 = 16
 
Path: 5 → 6 → 8 → 16

Visualizing as a tree:

The BIT can be visualized as a forest of trees rooted at powers of 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
                                16
                               / | \
                              /  |  \
                             8   12  14  15
                           / |\   |\   |
                          4 6 7  10 11 13
                         /| |    |
                        2 3 5    9
                        |
                        1
 
Each node stores the sum for its responsibility range:
- Node 16: sum of A[1..16]
- Node 8:  sum of A[1..8]
- Node 4:  sum of A[1..4]
- Node 12: sum of A[9..12]
- Node 6:  sum of A[5..6]
 
Update path: When updating A[i], follow i → parent(i) → parent(parent(i)) → ...
Query path:  Go in opposite direction (handled by subtracting LSB)

It's Not a Binary Tree!

Query Path — Traversing for Prefix Sums

Now we can understand how queries work. To compute prefix sum from 1 to i, we:

Start at index i
Add BIT[i] to our sum
Move to i - LSB(i) (strip the lowest set bit)
Repeat until i becomes 0

Why this works:

Each step collects a disjoint portion of the prefix sum. The ranges don't overlap because each index covers elements ending at that index.

Example: Query prefix sum [1..13]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Query prefix sum from 1 to 13:
 
Step 1: i = 13 (binary: 1101)
        BIT[13] covers A[13..13] (LSB = 1)
        Add BIT[13] to sum
        i = 13 - 1 = 12
 
Step 2: i = 12 (binary: 1100)
        BIT[12] covers A[9..12] (LSB = 4)
        Add BIT[12] to sum
        i = 12 - 4 = 8
 
Step 3: i = 8 (binary: 1000)
        BIT[8] covers A[1..8] (LSB = 8)
        Add BIT[8] to sum
        i = 8 - 8 = 0
 
Step 4: i = 0, STOP
 
Total: BIT[13] + BIT[12] + BIT[8]
     = A[13] + (A[9]+A[10]+A[11]+A[12]) + (A[1]+...+A[8])
     = A[1] + A[2] + ... + A[13] ✓
 
Ranges collected: [13..13], [9..12], [1..8]
These are disjoint and cover [1..13] exactly!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class FenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    /**
     * Query prefix sum from index 1 to i
     * 
     * The loop processes each set bit of i exactly once.
     * Since i has at most log₂(n) bits, this is O(log n).
     */
    query(i: number): number {
        let sum = 0;
        
        while (i > 0) {
            // BIT[i] covers the range [i - LSB(i) + 1, i]
            // Add this partial sum to our total
            sum += this.tree[i];
            
            // Remove the LSB from i
            // This moves us to the previous disjoint range
            // i & (i - 1) also strips the LSB, but i -= i & (-i) is clearer
            i -= i & (-i);
        }
        
        return sum;
    }
 
    // Range query [l, r] derived from prefix queries
    rangeQuery(l: number, r: number): number {
        // prefix(r) - prefix(l-1) gives exactly [l, r]
        return this.query(r) - this.query(l - 1);
    }
}
 
// Trace the query for i = 13
// i = 13 (1101₂): sum += tree[13], i = 13 - 1 = 12
// i = 12 (1100₂): sum += tree[12], i = 12 - 4 = 8
// i = 8  (1000₂): sum += tree[8],  i = 8 - 8 = 0
// i = 0: loop ends
// Total iterations: 3 = popcount(13) = number of set bits in 13

Number of Iterations = popcount(i)

The Mathematical Invariant

Let's formally state the invariant that makes Fenwick Trees work:

Invariant:

For any index i where 1 ≤ i ≤ n:

BIT[i] = Σ A[j] for all j in [i - LSB(i) + 1, i]

Equivalently:

BIT[i] = A[i - LSB(i) + 1] + A[i - LSB(i) + 2] + ... + A[i]

Corollary — Prefix Sum Formula:

prefix(i) = Σ BIT[k] where k traverses i → i - LSB(i) → ... → 0

The proof that this correctly computes prefix sums follows from:

Each BIT[k] in the traversal covers a disjoint range
The union of all traversed ranges equals exactly [1, i]
Therefore, the sum of BIT values equals the prefix sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * This function verifies that the BIT invariant holds.
 * For each index i, we check that BIT[i] equals the sum of the
 * expected range in the original array.
 */
function verifyBITInvariant(bit: number[], original: number[]): boolean {
    const n = original.length; // original is 1-indexed
    
    for (let i = 1; i <= n; i++) {
        const lsb = i & (-i);
        const rangeStart = i - lsb + 1;
        const rangeEnd = i;
        
        // Calculate expected sum for this range
        let expectedSum = 0;
        for (let j = rangeStart; j <= rangeEnd; j++) {
            expectedSum += original[j];
        }
        
        // Verify BIT[i] matches
        if (bit[i] !== expectedSum) {
            console.log(`Invariant violated at i=${i}`);
            console.log(`Expected: ${expectedSum}, Actual: ${bit[i]}`);
            return false;
        }
    }
    
    return true;
}
 
/**
 * This function verifies that prefix queries return correct results.
 */
function verifyPrefixQueries(bit: FenwickTree, original: number[]): boolean {
    const n = original.length - 1; // original is 1-indexed
    
    for (let i = 1; i <= n; i++) {
        // Calculate expected prefix sum
        let expected = 0;
        for (let j = 1; j <= i; j++) {
            expected += original[j];
        }
        
        const actual = bit.query(i);
        
        if (actual !== expected) {
            console.log(`Query mismatch at i=${i}`);
            console.log(`Expected: ${expected}, Actual: ${actual}`);
            return false;
        }
    }
    
    return true;
}

A Beautiful Decomposition

Memory Layout — Why It's Efficient

One of the Fenwick Tree's advantages is its memory efficiency. Let's examine why:

Space Comparison:

Memory Usage Comparison
Data Structure	Space	For n = 1,000,000 (64-bit integers)
Original Array	n elements	8 MB
Fenwick Tree	n + 1 elements	~8 MB (plus 8 bytes)
Prefix Sum Array	n elements	8 MB (but no updates!)
Segment Tree (typical)	4n elements	~32 MB
Segment Tree (optimized)	2n elements	~16 MB

Cache Efficiency:

Beyond raw size, Fenwick Trees have excellent cache performance:

Contiguous memory: The BIT is a simple array with excellent spatial locality
Predictable access patterns: Both query and update traverse indices in a predictable manner
Fewer cache lines touched: A query or update touches at most log₂(n) elements, often in nearby memory locations
No pointer chasing: Unlike tree-based structures, there are no pointers to follow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Memory-efficient Fenwick Tree implementation
 * Uses exactly (n + 1) * sizeof(element) bytes
 */
class MemoryEfficientBIT {
    // Single contiguous array - excellent cache behavior
    private readonly tree: number[];
    private readonly n: number;
 
    constructor(n: number) {
        this.n = n;
        // Allocate exactly n+1 elements (index 0 unused)
        this.tree = new Array(n + 1).fill(0);
    }
 
    // Notice: query and update both access memory in predictable patterns
    // For i = 13, query accesses: tree[13], tree[12], tree[8]
    // These indices decrease, giving good spatial locality
 
    update(i: number, delta: number): void {
        // Indices increase: 13 → 14 → 16 → ...
        // Increasing access pattern is cache-friendly
        for (; i <= this.n; i += i & (-i)) {
            this.tree[i] += delta;
        }
    }
 
    query(i: number): number {
        let sum = 0;
        // Indices decrease: 13 → 12 → 8
        // Decreasing access pattern still has good locality
        for (; i > 0; i -= i & (-i)) {
            sum += this.tree[i];
        }
        return sum;
    }
 
    // Memory footprint analysis
    getMemoryUsage(): number {
        // Each element is a 64-bit number (8 bytes in most contexts)
        return (this.n + 1) * 8; // bytes
    }
}
 
// Compare memory footprint
const n = 1_000_000;
const bit = new MemoryEfficientBIT(n);
console.log(`BIT memory: ${bit.getMemoryUsage() / 1024 / 1024} MB`);
console.log(`Segment tree would use: ${(4 * n * 8) / 1024 / 1024} MB`);
// BIT: ~8 MB, Segment Tree: ~32 MB

Summary — The Binary Index Structure

This page revealed the elegant mathematics that power Fenwick Trees. Here are the key takeaways:

Key Takeaways

•Binary representation determines the structure: each index covers a range whose length equals its lowest set bit (LSB).
•LSB(i) = i & (-i) extracts the lowest set bit using two's complement arithmetic — the fundamental operation in BITs.
•BIT[i] stores the sum of elements from (i - LSB(i) + 1) to i, a range of exactly LSB(i) elements.
•Query traversal strips LSB repeatedly (i -= i & (-i)), visiting exactly popcount(i) indices, which is O(log n).
•Update traversal goes the opposite direction (i += i & (-i)), propagating changes to all covering indices.
•The tree structure is implicit — stored as a flat array with parent relationships encoded in binary representation.
•Memory efficiency is excellent: exactly n+1 elements with superb cache locality.

What's next:

Page Complete

2 / 5