Fenwick Tree (Binary Indexed Tree) Explained

A Fenwick Tree, also known as a Binary Indexed Tree (BIT), maintains running prefix sums of an array while allowing point updates, both in O(log n). It does the same job as a sum segment tree for this specific task but with far less code and memory — a single array plus one bit trick. It is the standard answer when you need “update one element, query a prefix (or range) sum, repeatedly.”

The key trick: lowest set bit

Each index i (1-based) is responsible for a range of length equal to its lowest set bit, written i & (-i). For example index 6 = 110₂ has lowest set bit 2, so tree[6] covers the 2 elements ending at position 6. Walking by adding or subtracting this bit moves us through the tree in O(log n) steps.

int lowbit(int i) { return i & (-i); } // isolates the lowest set bit
// i = 6 (110)  -> lowbit = 2 (010)
// i = 12 (1100) -> lowbit = 4 (0100)

int lowbit(int i) { return i & (-i); } // isolates the lowest set bit
// i = 6 (110)  -> lowbit = 2 (010)
// i = 12 (1100) -> lowbit = 4 (0100)

function lowbit(i) { return i & (-i); } // isolates the lowest set bit
// i = 6 (110)  -> lowbit = 2 (010)
// i = 12 (1100) -> lowbit = 4 (0100)

def lowbit(i):
    return i & (-i)        # isolates the lowest set bit
# i = 6 (110)  -> lowbit = 2 (010)
# i = 12 (1100) -> lowbit = 4 (0100)

For beginners: Fenwick trees are 1-indexed internally. If your data is 0-indexed, add 1 when you call update/query. Index 0 is an unused sentinel.

Update: add a delta to one position

To add delta at position i, update tree[i], then jump to i + lowbit(i), repeating until you pass n. Each jump moves to the next node whose range covers i.

struct BIT {
    int n;
    std::vector<long long> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {}       // 1-indexed
    void update(int i, long long delta) {      // a[i] += delta
        for (; i <= n; i += i & (-i)) tree[i] += delta;
    }
};

class BIT {
    int n;
    long[] tree;
    BIT(int n) { this.n = n; tree = new long[n + 1]; } // 1-indexed
    void update(int i, long delta) {           // a[i] += delta
        for (; i <= n; i += i & (-i)) tree[i] += delta;
    }
}

class BIT {
  constructor(n) { this.n = n; this.tree = new Array(n + 1).fill(0); } // 1-indexed
  update(i, delta) {                           // a[i] += delta
    for (; i <= this.n; i += i & (-i)) this.tree[i] += delta;
  }
}

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)              # 1-indexed

    def update(self, i, delta):                # a[i] += delta
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

Query: prefix sum

The prefix sum of a[1..i] is the sum of tree values found by repeatedly subtracting the lowest set bit until we reach 0.

long long query(int i) {                       // sum of a[1..i]
    long long s = 0;
    for (; i > 0; i -= i & (-i)) s += tree[i];
    return s;
}
long long rangeSum(int l, int r) {             // sum of a[l..r]
    return query(r) - query(l - 1);
}

long query(int i) {                            // sum of a[1..i]
    long s = 0;
    for (; i > 0; i -= i & (-i)) s += tree[i];
    return s;
}
long rangeSum(int l, int r) {                  // sum of a[l..r]
    return query(r) - query(l - 1);
}

query(i) {                                     // sum of a[1..i]
  let s = 0;
  for (; i > 0; i -= i & (-i)) s += this.tree[i];
  return s;
}
rangeSum(l, r) {                               // sum of a[l..r]
  return this.query(r) - this.query(l - 1);
}

def query(self, i):                            # sum of a[1..i]
    s = 0
    while i > 0:
        s += self.tree[i]
        i -= i & (-i)
    return s

def range_sum(self, l, r):                     # sum of a[l..r]
    return self.query(r) - self.query(l - 1)

A range sum [l, r] is just query(r) - query(l - 1). Building from an existing array is n calls to update (O(n log n)), or an O(n) bottom-up fill if you need the speed.

Complexity

Operation	Time	Space
Point update	O(log n)	—
Prefix / range sum	O(log n)	—
Build	O(n log n)	O(n)

Common pitfalls

Off-by-one with 0-indexing. Always shift external indices by +1; querying index 0 returns 0 (the empty prefix), which is intended.
Storing values vs deltas. update adds a delta. To set a[i] = v, add v - current[i] and track the current value yourself.
Overflow. Use 64-bit accumulators for large sums.

Fenwick vs Segment Tree

Both give O(log n) updates and queries. The Fenwick tree is shorter, uses half the memory, and has tiny constants — but it natively handles only invertible aggregates (sum, xor) because range queries rely on subtraction. For min/max or range-assign updates, reach for a segment tree.

Test yourself on the advanced exercises.