Fenwick Trees:Prefix Updates When a Segment Tree Is More Tree Than You Need

A metrics board counts requests per minute. Each hit does counts[minute]++. Each chart asks “how many in the last hour?” Scanning the slice is O(n). Rebuilding a prefix array on every increment is also O(n). You need both: a point that moves, and a prefix that stays cheap.

A Fenwick tree (binary indexed tree, BIT) stores prefix aggregates in one array and walks them with least-significant-bit jumps. Point update and prefix query are O(log n). There are no node objects and no recursive build. You reach for it when the job is prefix-shaped and the operation has an inverse — not when you need an arbitrary range of a non-invertible op.

ADT vs implementation, Big-O, and the rest of the glossary live on the Data Structures Roadmap. This post is one layout: a 1-indexed array, i & -i, and range as two prefixes.

The prefix array that cannot update

If the counts never change after you fill them, a prefix array is the whole answer. prefix[i] is the sum of a[1]…a[i]. A range is subtraction. One pass, then O(1) reads.

long[] prefix = new long[n + 1];
for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + a[i];
}

long range(int left, int right) {
    return prefix[right] - prefix[left - 1];
}

The moment minute 42 gets another hit, every prefix[i] for i >= 42 is stale. Fixing that in this array is a walk to the end: O(n) per update. Static prefixes are an array. Live prefixes are a Fenwick tree.

Job	Cheap layout	Expensive layout
Prefix / range sum, then freeze	Prefix array	Re-summing the slice on every read
Point update + prefix (or range-via-prefix)	Fenwick tree	Rebuilding prefix[] on every write
Arbitrary range of min / max / gcd	Segment tree (not this post)	Scanning, or a Fenwick you force into the job

One array, LSB-sized ranges

Index the payload 1 … n. Leave tree[0] unused. tree[i] does not store a[i]. It stores the aggregate of a contiguous block that ends at i. The length of that block is the least significant 1-bit of i.

Call that length lsb(i) = i & -i. Then tree[i] covers a[i - lsb(i) + 1] … a[i].

i (binary)   lsb(i)   tree[i] covers
1  0001      1        a[1]
2  0010      2        a[1]..a[2]
3  0011      1        a[3]
4  0100      4        a[1]..a[4]
5  0101      1        a[5]
6  0110      2        a[5]..a[6]
7  0111      1        a[7]
8  1000      8        a[1]..a[8]

tree[4] is already a prefix of length 4. tree[6] is only the last two cells. A full prefix is a short chain of those blocks, not a scan of a.

Note: Two’s complement makes -i equal ~i + 1, so i & -i isolates the lowest set bit. That is arithmetic, not a tree pointer. Index 0 is unused because 0 & -0 is 0 and the jump would not move.

Jumps: i += i & -i and i -= i & -i

Two directions, same bit.

Update walks toward larger indexes: add the delta into every tree[i] whose range contains the point, then i += i & -i. Each step turns on a higher bit. You visit O(log n) cells.

Prefix query walks toward zero: add tree[i] into the answer, then i -= i & -i. Each step strips the lowest set bit. You add disjoint blocks that tile 1 … i.

prefix(6):  6 = 0110  add tree[6] (a[5]..a[6])
            i -= 2 → 4
            4 = 0100  add tree[4] (a[1]..a[4])
            i -= 4 → 0
            result = a[1]..a[6]

add(5, +3): 5 = 0101  tree[5] += 3
            i += 1 → 6
            6 = 0110  tree[6] += 3
            i += 2 → 8
            8 = 1000  tree[8] += 3
            … until i > n

Those two loops are the whole structure. No left child, no right child, no recursion. Height is the number of bits in n.

Prefix query and point update

Build is n point updates (or the same loop with the original values). After that, add and prefix are the hot path.

void add(long[] tree, int i, long delta) {
    while (i < tree.length) {
        tree[i] += delta;
        i += i & -i;
    }
}

long prefix(long[] tree, int i) {
    long sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= i & -i;
    }
    return sum;
}

Both are worst-case O(log n). Space is n + 1 longs. There is no java.util.FenwickTree; you write the array (or a thin class around it), the same way you write Union-Find.

A point read of a[i] is a range of length one: prefix(i) - prefix(i - 1). If you still hold the original a[], read that instead. The BIT is for aggregates, not a second copy of every cell unless you want it to be.

Range is two prefixes

Any contiguous sum is the difference of two prefixes. That is the same identity as the static prefix array. The Fenwick tree just keeps those prefixes honest after updates.

long range(long[] tree, int left, int right) {
    return prefix(tree, right) - prefix(tree, left - 1);
}

range(1, i) is prefix(i). range(i, i) is the current value at i. left = 1 and right = 0 never appear: prefix(0) is 0 because the query loop does not run.

This identity needs an inverse. Sum has subtraction. XOR has XOR. Min, max, and gcd do not have a cheap inverse, so prefix(r) - prefix(l - 1) is meaningless for them. That is the usual reason people open a segment tree instead — not because Fenwick is “weaker at sums.”

Java sketch

1-index the payload. Map real keys (minute numbers, SKU slots) onto 1 … n yourself. long avoids silent int overflow on busy counters.

final class FenwickTree {
    private final long[] tree; // 1-indexed; tree[0] unused

    FenwickTree(int n) {
        this.tree = new long[n + 1];
    }

    void add(int i, long delta) {
        while (i < tree.length) {
            tree[i] += delta;
            i += i & -i;
        }
    }

    long prefix(int i) {
        long sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & -i;
        }
        return sum;
    }

    long range(int left, int right) {
        return prefix(right) - prefix(left - 1);
    }
}

Seven minutes, then a late hit on minute 5 and a last-hour style range:

FenwickTree minutes = new FenwickTree(7);
minutes.add(1, 3);
minutes.add(2, 2);
minutes.add(3, -1);
minutes.add(4, 6);
minutes.add(5, 5);
minutes.add(6, 4);
minutes.add(7, -3);

System.out.println(minutes.prefix(6));     // 19
minutes.add(5, 3);                         // late increment
System.out.println(minutes.range(4, 6));   // 18

19
18

prefix(6) was 3+2+(-1)+6+5+4 = 19. After add(5, 3), range(4, 6) is 6 + 8 + 4 = 18. Three LSB jumps on the update; two prefixes on the range. No rescan.

Note: add takes a delta, not a replacement. To set a[i] = v when you still know the old value, add v - old. If you dropped a[], read the old value as range(i, i) first.

When not to use a Fenwick tree

Skip it when the job is not “live prefix of an invertible op”:

• The array is static. Build prefix[] once. A Fenwick tree is extra code for a freeze you already paid for.
• Arbitrary range of a non-invertible operation — min, max, gcd on [L, R] with updates. You cannot recover that from two prefixes. That is the segment-tree job: a real tree of range nodes. This series will cover that layout separately; do not stretch LSB jumps to fake it.
• You needed a full sort or a next-best item — different hot operations, different layouts (sorted map, heap). A BIT answers aggregates on indexes, not “who is next?”
• n is tiny and the loop is already there. Summing forty buckets is clearer than explaining i & -i. Measure when the counters grow.

Fenwick can be extended (difference array plus a BIT for range-add / point-query, or two BITs for range-add / range-sum). Those are the same jumps with a second array. They are not a reason to start here if a prefix array or a scan already fits.

Reach for Fenwick when point updates and prefix-shaped sums (or XOR) share the hot path and you want O(log n) without building a segment tree.

Cheat sheet

Layout:     tree[i] = aggregate of a[i - lsb(i) + 1 .. i]; 1-indexed
lsb:        i & -i  (lowest set bit; two's complement)
Update:     tree[i] += delta; i += i & -i          O(log n)
Prefix:     sum += tree[i]; i -= i & -i            O(log n)
Range:      prefix(r) - prefix(l - 1)              needs an inverse
Point set:  add(v - old), not a second API
Space:      n + 1 (tree[0] unused)
JDK:        none — you write the array
Good:       live prefix/range sums, XOR, frequency on mapped indexes
Avoid:      static prefixes (plain prefix[]); min/max/gcd ranges (segment tree)

Do:

• Index 1 … n. Map real keys in a table you own.
• Treat add as a delta. Keep a[] if you replace values often.
• Use long for sums that can exceed Integer.MAX_VALUE.

Don’t:

• Rebuild a prefix array on every increment and call it a range query.
• Ask a Fenwick tree for range minimum. No inverse, no prefix(r) - prefix(l - 1).
• 0-index the BIT and then wonder why i & -i never moves.

Wrap-up

A Fenwick tree is a prefix machine in an array. Each tree[i] holds an LSB-sized block; update jumps with i += i & -i, query strips bits with i -= i & -i, and a range is two prefixes when the operation has an inverse. Point update and prefix query stay O(log n) without node objects or a recursive build.

If the data never moves after the first pass, a prefix array is enough. If the query is an arbitrary range of min or max, you want a segment tree, not a BIT stretched past subtraction. If the hot path is live sums (or XOR) on indexes, Fenwick is the smaller layout that makes that cheap. Glossary and the series index live on the Data Structures Roadmap.

Next optional step in the series Same component without building an adjacency list. Union-Find: Connected Components →