Fenwick Tree (BIT)
Compact structure for prefix sum queries and point updates in O(log n).
How it works
A Fenwick Tree (also called a Binary Indexed Tree or BIT) is an array-based data structure that supports two operations in O(log n) time:
1. Prefix sum query — sum of elements from index 1 to i 2. Point update — add a delta to a single element
The key insight is the lowbit function: `lowbit(i) = i & (-i)` isolates the least significant set bit of i. Each cell BIT[i] stores the sum of elements in the range `(i − lowbit(i), i]`. To query, subtract lowbit repeatedly. To update, add lowbit repeatedly. This halves the work at each step, giving O(log n) performance with O(n) space.
Complexity
Visualizer
Where it's used in the real world
Competitive programming / Online judges
Dynamic prefix sum / frequency tablesFenwick Trees are the go-to structure for problems requiring O(log n) prefix sums with point updates — inversions count, order statistics, 2D range queries.
Apache Lucene / search engines
Cumulative frequency tables for term statisticsBITs appear in statistical ranking models where cumulative term frequencies need fast incremental updates as documents are indexed.
Game engines
Weighted random samplingA BIT can implement alias-method-like weighted sampling: query gives cumulative weight, update changes a weight, binary search on the BIT finds the sampled index — all in O(log n).
Database systems
Histogram maintenanceIncrementally updated histograms (e.g. for query planning statistics) can be maintained with a BIT so range-bucket queries remain fast without rebuilding from scratch.
Implementation
class FenwickTree {
private bit: number[];
private n: number;
constructor(n: number) {
this.n = n;
this.bit = new Array(n + 1).fill(0); // 1-indexed
}
// Add delta to position i (1-indexed)
update(i: number, delta: number): void {
for (; i <= this.n; i += i & -i)
this.bit[i] += delta;
}
// Prefix sum [1, i] (1-indexed)
query(i: number): number {
let sum = 0;
for (; i > 0; i -= i & -i)
sum += this.bit[i];
return sum;
}
// Range sum [l, r] (1-indexed)
rangeQuery(l: number, r: number): number {
return this.query(r) - this.query(l - 1);
}
}
// Build from array
const arr = [3, 2, -1, 6, 5, 4, -3, 3];
const ft = new FenwickTree(arr.length);
arr.forEach((val, i) => ft.update(i + 1, val));
console.log(ft.rangeQuery(1, 5)); // 15
ft.update(4, 2); // arr[3] += 2
console.log(ft.rangeQuery(1, 5)); // 17