Introduction

A Binary Indexed Tree, also called a Fenwick tree, is a compact data structure for prefix sums with point updates. It is useful when you need to update array values and query cumulative totals repeatedly, because both operations run in O(log n) time.

Core Sections

What problem a BIT solves

Suppose you have an array of numbers and need two operations many times:

• add a value at one index
• ask for the sum from the beginning up to index i

A plain array makes updates cheap but repeated prefix sums expensive. A precomputed prefix array makes queries cheap but updates expensive. A Binary Indexed Tree sits in the middle and makes both efficient enough for dynamic workloads.

Why the structure works

A BIT stores partial sums in a 1-indexed array. Each position is responsible for a range whose size is determined by the lowest set bit of the index.

The bit trick used everywhere is:

index & -index

That value tells you how large the covered segment is and how to move through the tree structure embedded inside the array.

Core operations in C++

1#include <iostream>
2#include <vector>
3
4class FenwickTree {
5public:
6    explicit FenwickTree(int n) : bit(n + 1, 0) {}
7
8    void add(int index, int delta) {
9        for (; index < bit.size(); index += index & -index) {
10            bit[index] += delta;
11        }
12    }
13
14    int prefixSum(int index) const {
15        int sum = 0;
16        for (; index > 0; index -= index & -index) {
17            sum += bit[index];
18        }
19        return sum;
20    }
21
22    int rangeSum(int left, int right) const {
23        return prefixSum(right) - prefixSum(left - 1);
24    }
25
26private:
27    std::vector<int> bit;
28};
29
30int main() {
31    FenwickTree tree(5);
32    tree.add(1, 5);
33    tree.add(2, 3);
34    tree.add(5, 7);
35
36    std::cout << tree.prefixSum(2) << '\n';
37    std::cout << tree.rangeSum(2, 5) << '\n';
38}

This version supports point updates and range-sum queries through two prefix sums.

Think in one-based indexing

Fenwick trees are typically implemented with indices starting at 1. That is not arbitrary. The parent and next-update relationships rely on the bit pattern of the index, and the arithmetic becomes clean with one-based indexing.

If your original array is zero-based, convert when calling the tree.

// original zero-based index i
fenwick.add(i + 1, delta);

Trying to force a zero-based BIT usually creates more confusion than it saves.

When a BIT is a good fit

A Fenwick tree is ideal when you need:

• prefix sums
• point updates
• range sums derived from prefix sums
• coordinate-compressed frequency counting

It is popular in competitive programming for inversion counting, dynamic frequency tables, and order-statistics style problems after compression.

If you need arbitrary range updates plus arbitrary range queries, or operations like minimum over a range with updates, a segment tree may be the better tool.

Why it is often preferred over a segment tree

A BIT is shorter to implement, uses less memory, and is easier to debug for prefix-sum style problems. A segment tree is more general, but if the problem is exactly “prefix or range sum with point updates,” the Fenwick tree is often the cleaner answer.

Common Pitfalls

• Forgetting that most Fenwick tree implementations are intentionally one-indexed.
• Using the wrong update or query loop direction and breaking the index & -index traversal logic.
• Expecting the structure to handle arbitrary range-query types when it is really specialized for prefix-style aggregation.
• Mixing zero-based problem indices with one-based tree indices without converting consistently.
• Reaching for a segment tree immediately when a simpler BIT would solve the required point-update and prefix-sum problem.

Summary

• A Binary Indexed Tree supports point updates and prefix sums in O(log n) time.
• It works by storing partial sums in a one-indexed array using the lowest-set-bit trick.
• Range sums are computed from two prefix sums.
• Fenwick trees are simpler and smaller than segment trees for the right class of problems.
• Most implementation bugs come from indexing mistakes rather than from the core algorithm.