Fenwick Tree (Binary Indexed Tree)

Say you have a big list of numbers. People keep asking you “what is the sum of the first 7 numbers?” At the same time, someone keeps changing a number in the list. Now what? If you add up the numbers one by one every single time, each answer takes O(n) work. That feels slow when the list is huge and the questions keep coming. A Fenwick Tree fixes exactly this pain. It answers those sum questions and handles those changes in O(log n) time each.

🌳 A Real-World Picture

Think of a shop that tracks sales for each day of the month. The manager keeps asking “how much did we sell from day 1 to day 12?” And the cashier keeps correcting numbers because a return came in on day 5.

If you store sales day by day, every “total so far” question makes you walk through all those days again. A Fenwick Tree is like keeping a few smart running totals. Each total covers a neat block of days. So when someone asks for day 1 to 12, you just add up a small handful of those blocks instead of all 12 days. And when day 5 changes, you only touch the few blocks that include day 5.

A Fenwick Tree, also called a Binary Indexed Tree (or BIT for short), is an array where each slot quietly stores the sum of a range of original values. The size of that range is decided by one clever bit trick.

🎯 What Problem Does It Solve?

You hit this problem whenever both these things happen on the same list:

• You want the prefix sum, which means the sum from the start up to some index.
• The values keep changing while the questions keep coming.

A plain array gives you fast prefix sums only if nothing changes. The moment a value updates, the easy trick breaks. Each option has a catch.

See the problem with the first two rows? One is fast to read but slow to change. The other is fast to change but slow to read. The Fenwick Tree stays fast on both. That balance is the whole point.

🔑 The Low-Bit Trick

Everything in a Fenwick Tree rests on one small idea. It is the lowest set bit. The lowest set bit of a number is the smallest 1 in its binary form, kept on its own with everything above it turned off.

You get it with this:

lowbit(index) = index & (-index)

Why does that work? Because -index in a computer is the bitwise flip of index plus one. When you AND them together, only the lowest 1 survives. Let us see it for the number 12:

 12 = 0000 1100
-12 = 1111 0100
 12 & -12 = 0000 0100 = 4

So lowbit(12) is 4. In a Fenwick Tree, this number tells you how big a block that slot is responsible for. Slot 12 stores the sum of 4 values: index 9, 10, 11, and 12.

Here is a small tree for 8 values. Each slot covers the range shown.

➕ How Update Works

Now say one value changes. You need to fix every slot whose block contains that index. The trick is to keep jumping up by the lowest set bit.

The rule for update is:

index += index & (-index)

You start at the index you changed. You add the change to that slot. Then you jump to the next slot by adding the lowest set bit. You repeat until you walk off the end of the array. Each jump lands on the next slot that also covers your index. So you never miss one and never visit extra ones.

Steps to update index i by adding delta:

1. Start at i.
2. Add delta to tree[i].
3. Move to the next slot: i = i + (i & -i).
4. Repeat steps 2 and 3 while i is within the array.

🔎 How Prefix Sum Works

To get the prefix sum up to index i, you go the other way. You keep subtracting the lowest set bit, collecting block sums as you walk down to zero.

The rule for query is:

index -= index & (-index)

Each step grabs the block that ends at the current index, then jumps back to just before that block. When the index reaches 0, you stop. You have collected a small set of non-overlapping blocks that together cover everything from 1 up to i.

Steps to get the prefix sum up to index i:

1. Start at i with a running sum of 0.
2. Add tree[i] to sum.
3. Move down: i = i - (i & -i).
4. Repeat steps 2 and 3 while i is greater than 0.
5. Return sum.

💻 Building a Fenwick Tree

Let us put it together. We will build a tree from the values [3, 2, -1, 6, 5, 4, -3, 3], then ask for the prefix sum up to index 5, then add 4 to index 3, then ask again. The prefix sum up to index 5 is 3 + 2 + (-1) + 6 + 5 = 15. After adding 4 to index 3, that same prefix becomes 19.

#include <stdio.h>

#define N 8
int tree[N + 1]; // 1-indexed, index 0 stays empty

// Add delta at position i by walking up the tree
void update(int i, int delta) {
    for (; i <= N; i += i & (-i))
        tree[i] += delta;
}

// Sum of values from index 1 up to i
int prefixSum(int i) {
    int sum = 0;
    for (; i > 0; i -= i & (-i))
        sum += tree[i];
    return sum;
}

int main(void) {
    int values[N] = {3, 2, -1, 6, 5, 4, -3, 3};

    // Build the tree by updating each position once
    for (int i = 0; i < N; i++)
        update(i + 1, values[i]);

    printf("Prefix sum up to index 5: %d\n", prefixSum(5));
    update(3, 4); // add 4 to the value at index 3
    printf("After adding 4 at index 3: %d\n", prefixSum(5));
    return 0;
}

Prefix sum up to index 5: 15
After adding 4 at index 3: 19

#include <iostream>
#include <vector>
using namespace std;

const int N = 8;
vector<int> tree(N + 1, 0); // 1-indexed, index 0 stays empty

// Add delta at position i by walking up the tree
void update(int i, int delta) {
    for (; i <= N; i += i & (-i))
        tree[i] += delta;
}

// Sum of values from index 1 up to i
int prefixSum(int i) {
    int sum = 0;
    for (; i > 0; i -= i & (-i))
        sum += tree[i];
    return sum;
}

int main() {
    vector<int> values = {3, 2, -1, 6, 5, 4, -3, 3};

    // Build the tree by updating each position once
    for (int i = 0; i < N; i++)
        update(i + 1, values[i]);

    cout << "Prefix sum up to index 5: " << prefixSum(5) << endl;
    update(3, 4); // add 4 to the value at index 3
    cout << "After adding 4 at index 3: " << prefixSum(5) << endl;
    return 0;
}

Prefix sum up to index 5: 15
After adding 4 at index 3: 19

public class Fenwick {
    static final int N = 8;
    static int[] tree = new int[N + 1]; // 1-indexed, index 0 stays empty

    // Add delta at position i by walking up the tree
    static void update(int i, int delta) {
        for (; i <= N; i += i & (-i))
            tree[i] += delta;
    }

    // Sum of values from index 1 up to i
    static int prefixSum(int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i))
            sum += tree[i];
        return sum;
    }

    public static void main(String[] args) {
        int[] values = {3, 2, -1, 6, 5, 4, -3, 3};

        // Build the tree by updating each position once
        for (int i = 0; i < N; i++)
            update(i + 1, values[i]);

        System.out.println("Prefix sum up to index 5: " + prefixSum(5));
        update(3, 4); // add 4 to the value at index 3
        System.out.println("After adding 4 at index 3: " + prefixSum(5));
    }
}

Prefix sum up to index 5: 15
After adding 4 at index 3: 19

N = 8
tree = [0] * (N + 1)  # 1-indexed, index 0 stays empty


def update(i, delta):
    # Add delta at position i by walking up the tree
    while i <= N:
        tree[i] += delta
        i += i & (-i)


def prefix_sum(i):
    # Sum of values from index 1 up to i
    total = 0
    while i > 0:
        total += tree[i]
        i -= i & (-i)
    return total


values = [3, 2, -1, 6, 5, 4, -3, 3]

# Build the tree by updating each position once
for idx, value in enumerate(values):
    update(idx + 1, value)

print("Prefix sum up to index 5:", prefix_sum(5))
update(3, 4)  # add 4 to the value at index 3
print("After adding 4 at index 3:", prefix_sum(5))

Prefix sum up to index 5: 15
After adding 4 at index 3: 19

const N = 8;
const tree = new Array(N + 1).fill(0); // 1-indexed, index 0 stays empty

// Add delta at position i by walking up the tree
function update(i, delta) {
  for (; i <= N; i += i & -i) tree[i] += delta;
}

// Sum of values from index 1 up to i
function prefixSum(i) {
  let sum = 0;
  for (; i > 0; i -= i & -i) sum += tree[i];
  return sum;
}

const values = [3, 2, -1, 6, 5, 4, -3, 3];

// Build the tree by updating each position once
values.forEach((value, idx) => update(idx + 1, value));

console.log("Prefix sum up to index 5:", prefixSum(5));
update(3, 4); // add 4 to the value at index 3
console.log("After adding 4 at index 3:", prefixSum(5));

Prefix sum up to index 5: 15
After adding 4 at index 3: 19

⏱️ Why It Is O(log n)

Look at the loops. Each step clears or moves the lowest set bit of the index. A number has about log n bits. So you take at most about log n steps before you run off the end or reach zero.

⚖️ Fenwick Tree vs Segment Tree

People often ask which one to use. Both give O(log n) updates and queries. In short:

• A Segment Tree is more general. It handles min, max, gcd, and many other range questions, not just sums.
• A Fenwick Tree only does the operations that can be undone neatly, like sum. But it is much simpler to write and uses less memory.

So for plain prefix sums or range sums with updates, reach for a Fenwick Tree. When you need range min, range max, or lazy range updates, the Segment Tree is the right tool.

⚠️ Common Mistakes

A few traps trip up almost everyone the first time:

• Using 0-based indexing. The Fenwick Tree must be 1-indexed, because lowbit(0) is 0 and your loop would never move. Always shift your values up by one.
• Sizing the array as n instead of n + 1. You need that extra slot for the 1-based layout.
• Confusing the two loops. Update goes up (+=), query goes down (-=). Swap them and your answers go wrong silently.
• Storing the value instead of the change in update. The update function adds a delta. To set a position to a new value, add the difference between the new and old value, not the new value itself.

🧩 What You’ve Learned

• ✅ A Fenwick Tree (Binary Indexed Tree) gives both prefix-sum queries and point updates in O(log n) time.
• ✅ The whole thing runs on the lowest set bit, found with index & (-index).
• ✅ Update walks up with i += i & (-i). Query walks down with i -= i & (-i).
• ✅ A range sum from l to r is just prefixSum(r) - prefixSum(l - 1).
• ✅ It is 1-indexed, uses O(n) memory, and is simpler and lighter than a Segment Tree for sum-type questions.

🚀 What’s Next?

• Segment Tree
• Prefix Sum Technique