Fenwick tree (BIT)
hardNode i covers the last (i & −i) elements ending at i - the binary representation of the index *is* the range decomposition. Half the code and half the memory of a segment tree.
O(log n)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How fenwick tree (bit) works
A Fenwick tree is a single 1-indexed array with one rule: tree[i] holds the sum of the last (i & -i) elements ending at position i. That expression isolates the lowest set bit, so index 8 (binary 1000) covers eight elements, index 6 (110) covers two, and index 5 (101) covers one. The binary representation of the index is the range decomposition - no pointers, no node objects.
prefix(i) walks by stripping the lowest set bit until the index reaches zero: the sum through 1-based position 7 (binary 111) reads tree[7], tree[6], tree[4] - one read per set bit. Update mirrors the walk upward: i += i & -i visits exactly the ranges that cover position i. Both loops run at most log n times, and a range sum is prefix(r) minus prefix(l-1).
Against a segment tree it is half the code and half the memory: one array of n+1 integers, two four-line loops, no recursion. The limit is that range queries subtract one prefix from another, which demands an invertible operation. Sums and counts qualify; minimum does not - there is no way to un-min a value. Within that boundary it is the sharpest tool available.
Step by step
- Start with values [3, 2, 5, 1, 7, 4, 6, 2] and a zeroed tree array of nine cells, used from index 1 to 8.
- Build by point updates. Adding a[0] = 3 at position 1 touches tree[1], tree[2], tree[4], tree[8] - each jump adds the lowest set bit.
- After all eight updates, tree[4] holds a[0..3] = 11 and tree[8] holds the full sum, 30.
- Query prefix(6) - 1-based position 7, binary 111. Read tree[7] = 6, covering a[6..6]. Strip the low bit: 7 becomes 6.
- Read tree[6] = 11, covering a[4..5]. Running total 17. Strip again: 6 (110) becomes 4 (100).
- Read tree[4] = 11, covering a[0..3]. Total 28. Strip once more: 4 becomes 0, so the loop stops.
- prefix(6) = 28 from exactly three reads - one per set bit in 111. A direct scan of a[0..6] confirms 28.
Complexity
| Worst case time | O(log n) |
|---|---|
| Space | O(n) |
Each step strips or adds one set bit, so at most log n iterations.
Reference implementation
Python
class Fenwick:
"""Prefix sums with point updates, both O(log n), in n words."""
def __init__(self, n):
self.n = n
self.t = [0] * (n + 1) # 1-indexed
def update(self, i, delta):
i += 1 # caller uses 0-indexing
while i <= self.n:
self.t[i] += delta
i += i & -i # next range that covers i
def prefix(self, i):
"""Sum of a[0..i] inclusive."""
i += 1
total = 0
while i > 0:
total += self.t[i]
i -= i & -i # strip lowest set bit
return total
def range_sum(self, l, r):
return self.prefix(r) - self.prefix(l - 1) if l else self.prefix(r)JavaScript
class Fenwick {
constructor(n) { this.n = n; this.t = new Array(n + 1).fill(0); }
update(i, delta) {
for (i++; i <= this.n; i += i & -i) this.t[i] += delta;
}
prefix(i) {
let total = 0;
for (i++; i > 0; i -= i & -i) total += this.t[i];
return total;
}
rangeSum(l, r) { return this.prefix(r) - (l ? this.prefix(l - 1) : 0); }
}Worth noticing
Node i covers the last (i & −i) elements ending at i
That is the entire design. Index 8 (binary 1000) covers eight elements; index 6 (110) covers two; index 5 (101) covers one. The binary representation of the index *is* the range decomposition.
Stripping bits walks the decomposition
prefix(11) = tree[11] + tree[10] + tree[8], because 1011 → 1010 → 1000 → 0. Each step removes one set bit, so the loop runs once per 1 in the index - at most log n times.
Half the code of a segment tree, half the memory
A Fenwick tree is one array of n+1 integers with no explicit nodes, no recursion and excellent cache behaviour. It is the right choice whenever you only need prefix-style queries with an invertible operation.
But it cannot do everything a segment tree can
Range minimum has no inverse, so you cannot subtract one prefix from another to get a range. That is where the segment tree earns its extra complexity.
Common pitfalls
- Index 0. The internal array is 1-based because i & -i is 0 when i is 0 - an update loop entered at index 0 never advances. Shift caller indices by one at the boundary.
- Treating update as assignment. It adds a delta; to set a[i] to v you must fetch the old value and add v minus it.
- Using it for range minimum. prefix(r) minus prefix(l-1) requires an inverse, and min has none - that job needs a segment tree or a sparse table.
- Sizing the array at n instead of n+1 - position n, the widest-covering cell, silently indexes out of range.
- Building with n updates costs O(n log n). Usually fine, but an O(n) build exists: copy the values in, then push each tree[i] into its parent at i + (i & -i).
Where it is used
- Counting inversions: sweep the array, query how many already-seen values exceed the current one, then update its position.
- Order statistics over a changing multiset - how many elements are at most x, in O(log n) per question.
- Live cumulative frequency tables: histograms, rank trackers, and the adaptive models inside arithmetic coding.
- The competitive-programming default whenever point update plus prefix sum is the entire requirement.
Frequently asked questions
What is the time and space complexity of a Fenwick tree?
Update and prefix query are O(log n) worst case - each loop iteration strips or adds one set bit, and an index has at most log n of them. Space is O(n): a single array of n+1 integers, with none of the 4n overhead a segment tree carries.
What does i & -i actually do?
It isolates the lowest set bit. In two's complement, -i flips every bit above the lowest 1 and keeps that 1, so the AND leaves only it: 6 is 110, -6 ends in 010, and 6 & -6 = 2. That value is both the size of tree[i]'s range and the step to the next index.
What is the difference between a Fenwick tree and a segment tree?
A Fenwick tree is one array, shorter code, and lower memory, but it only answers prefix-decomposable queries with an invertible operation. A segment tree spends 4n space and more code to support min, max, and gcd directly, plus lazy range updates. If point update plus prefix sum is the whole job, Fenwick wins on simplicity.
How do you compute the sum of a range l..r?
Take prefix(r) and subtract prefix(l - 1) - two O(log n) walks. This works because addition has an inverse; the same subtraction trick fails for minimum. Guard the l = 0 edge, where there is no earlier prefix to subtract and prefix(r) alone is the answer.