Fenwick Trees

A Fenwick tree does prefix-sum queries and updates with startlingly little code — once you see the binary-indexing trick.

The problem

You're tallying votes in real time. Every second, ballots land for various candidates, and a dashboard needs the running total for "candidates 1 through k" constantly. Counts change, and prefix sums are read just as often. It's the classic point-update, prefix-query workload.

A segment tree would nail it in O(log n). But you're doing this on a memory-tight embedded box, and honestly, the segment tree's 4n array and the recursion feel heavy for a job this plain. You just want prefix sums that update fast, with as little machinery as possible.

A first attempt

Keep a running prefix-sum array. Query is one lookup — O(1). But a single point update ripples:

def update(prefix, i, delta):
    for j in range(i, len(prefix)):
        prefix[j] += delta   # O(n) per update

Every candidate after i shifts, so each update is O(n). Flip it and store raw counts instead: updates become O(1), but a prefix query now sums i elements — O(n) again. The same read/write tug-of-war from the segment tree lesson. You want both in O(log n) — but lighter.

The insight

Here's the trick. Instead of each slot owning one element (raw counts) or all preceding elements (prefix sums), let slot i own a carefully chosen block of elements ending at i — and let the size of that block be dictated by the binary representation of i.

Specifically, slot i covers the i & (-i) elements ending at i, where i & (-i) isolates the lowest set bit of i. A prefix sum for [1..i] then stitches together a few of these blocks by repeatedly stripping off the lowest set bit — and there are only as many blocks as there are 1-bits in i, at most log n of them. Updates walk the mirror path, adding the lowest set bit each step. Two tiny loops, one array of size n+1. That's a Fenwick tree (a.k.a. binary indexed tree).

How it works

Slot i covers `i & (-i)` elements ending at i

i & (-i) isolates the lowest set bit. So slot 6 (110) has lowest bit 2 and covers 2 elements: indices 5–6. Slot 8 (1000) has lowest bit 8 and covers 8 elements: 1–8. The whole array is a 1-indexed bit of size n+1.

i:      1   2   3   4   5   6   7   8
bits: 001 010 011 100 101 110 111 1000
cover: [1][1-2][3][1-4][5][5-6][7][1-8]

Prefix sum strips the lowest bit each step

To sum [1..i], add bit[i], then jump to i - (i & -i) and repeat until i is 0. Each jump clears one 1-bit, so you visit one block per set bit — O(log n).

prefix(6):  bit[6]  covers 5-6
            6 -> 4
            bit[4]  covers 1-4
            4 -> 0  stop   =>  sum of 1..6

Update adds the lowest bit each step

To add delta at index i, update bit[i], then jump to i + (i & -i) and repeat while i <= n. You touch exactly the slots whose blocks contain i — again O(log n).

Range sum is a subtraction

sum(l..r) = prefix(r) - prefix(l - 1). This works only because sum has an inverse. Min and max don't — which is why they belong on a segment tree, not a Fenwick tree.

The code

Zero-indexed public API (inputs shift to the 1-indexed bit internally).

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

    def update(self, i, delta):   # add delta at 0-indexed position i
        i += 1
        while i <= self.n:
            self.bit[i] += delta
            i += i & (-i)

    def prefix_sum(self, i):      # sum of data[0..i] inclusive
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & (-i)
        return s

    def range_sum(self, l, r):    # sum of data[l..r] inclusive
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

class FenwickTree {
  private n: number;
  private bit: number[];

  constructor(n: number) {
    this.n = n;
    this.bit = new Array(n + 1).fill(0); // 1-indexed internally
  }

  update(i: number, delta: number): void {
    for (i += 1; i <= this.n; i += i & -i) this.bit[i] += delta;
  }

  prefixSum(i: number): number {
    let s = 0;
    for (i += 1; i > 0; i -= i & -i) s += this.bit[i];
    return s;
  }

  rangeSum(l: number, r: number): number {
    return this.prefixSum(r) - this.prefixSum(l - 1);
  }
}

class FenwickTree {
    private final int n;
    private final long[] bit;

    FenwickTree(int n) {
        this.n = n;
        bit = new long[n + 1]; // 1-indexed internally
    }

    void update(int i, long delta) {
        for (i += 1; i <= n; i += i & (-i)) bit[i] += delta;
    }

    long prefixSum(int i) {
        long s = 0;
        for (i += 1; i > 0; i -= i & (-i)) s += bit[i];
        return s;
    }

    long rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
}

#include <stdlib.h>

typedef struct {
    int n;
    long long *bit; /* 1-indexed internally */
} Fenwick;

Fenwick *fen_create(int n) {
    Fenwick *f = malloc(sizeof(Fenwick));
    f->n = n;
    f->bit = calloc(n + 1, sizeof(long long));
    return f;
}

void fen_update(Fenwick *f, int i, long long delta) {
    for (i += 1; i <= f->n; i += i & (-i)) f->bit[i] += delta;
}

long long fen_prefix_sum(Fenwick *f, int i) {
    long long s = 0;
    for (i += 1; i > 0; i -= i & (-i)) s += f->bit[i];
    return s;
}

long long fen_range_sum(Fenwick *f, int l, int r) {
    return fen_prefix_sum(f, r) - fen_prefix_sum(f, l - 1);
}

#include <vector>
using namespace std;

class FenwickTree {
    int n;
    vector<long long> bit; // 1-indexed internally

public:
    FenwickTree(int n) : n(n), bit(n + 1, 0) {}

    void update(int i, long long delta) {
        for (i += 1; i <= n; i += i & (-i)) bit[i] += delta;
    }

    long long prefixSum(int i) {
        long long s = 0;
        for (i += 1; i > 0; i -= i & (-i)) s += bit[i];
        return s;
    }

    long long rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
};

Complexity

Operation	Time	Space
Build (n updates)	O(n log n)	O(n)
Point update	O(log n)	O(1)
Prefix / range query	O(log n)	O(1)

Space is just n + 1 — no 4n, no recursion stack. That leanness is the whole appeal.

When to use it

Fenwick tree when sums are enough; segment tree when they aren't

For point-update plus prefix-or-range sum, a Fenwick tree is the lightest tool: half the memory of a segment tree, iterative, cache-friendly, a dozen lines. But it leans on subtraction, so it can't do min or max, and range updates need a second BIT and a cleverer setup. When your operation has no inverse, or you need arbitrary range assignment, go back to the segment tree with lazy propagation.

Practice

Recap

A Fenwick tree gives O(log n) point updates and prefix/range sums in n + 1 space and a handful of iterative lines — no recursion, no 4n array.
The engine is i & (-i): it isolates the lowest set bit, sizing each slot's block and stepping the update (+) and query (−) walks.
It's the right pick for invertible aggregates like sum; for min, max, or range assignment, reach for a segment tree instead.

Fenwick Trees

The problem

A first attempt

The insight

How it works

Slot i covers `i & (-i)` elements ending at i

Prefix sum strips the lowest bit each step

Update adds the lowest bit each step

Range sum is a subtraction

The code

Complexity

When to use it

Practice

Recap

Segment Trees

Segment Tree Queries

Lazy Propagation

On this page

Fenwick Trees

What does `i & (-i)` actually compute, and why the lowest set bit?

Why must a Fenwick tree be 1-indexed internally?

You need range minimum queries with point updates. Fenwick or segment tree?

Segment Trees

Segment Tree Queries

Lazy Propagation

On this page