Pattern Guide
Fenwick Tree (BIT)
"Range sum and point update in O(log n). Simpler than segment tree for prefix queries."
A Fenwick Tree (Binary Indexed Tree / BIT) supports prefix sum queries and point updates in O(log n) using a flat array. Each index stores the sum of a specific range of elements determined by the lowest set bit. Simpler to code than a segment tree, but limited to commutative/invertible operations (sum, XOR, product mod p). Extends to 2D BIT for matrix queries.
Problems you can solve with this pattern
5 problems · click any to start solving
// 1D Fenwick Tree (1-indexed)
class BIT {
constructor(n) { this.n = n; this.tree = new Array(n + 1).fill(0); }
update(i, delta) {
for (; i <= this.n; i += i & (-i)) this.tree[i] += delta;
}
query(i) { // prefix sum [1..i]
let s = 0;
for (; i > 0; i -= i & (-i)) s += this.tree[i];
return s;
}
rangeQuery(l, r) { return this.query(r) - this.query(l - 1); }
// Point query (when using BIT as difference array):
// update(l, +1), update(r+1, -1) → query(i) gives range add value at i
}
// 2D Fenwick Tree
class BIT2D {
constructor(m, n) { this.m = m; this.n = n; this.t = Array.from({length:m+1},()=>new Array(n+1).fill(0)); }
update(r, c, v) {
for (let i = r; i <= this.m; i += i & (-i))
for (let j = c; j <= this.n; j += j & (-j))
this.t[i][j] += v;
}
query(r, c) {
let s = 0;
for (let i = r; i > 0; i -= i & (-i))
for (let j = c; j > 0; j -= j & (-j))
s += this.t[i][j];
return s;
}
rangeQuery(r1, c1, r2, c2) {
return this.query(r2,c2) - this.query(r1-1,c2) - this.query(r2,c1-1) + this.query(r1-1,c1-1);
}
}A BIT stores partial sums where bit[i] covers the range [i - lowbit(i) + 1, i], where lowbit(i) = i & (-i). Update: propagate change upward by repeatedly adding lowbit. Query: sum prefix [1..i] by walking down, subtracting lowbit. Both operations touch O(log n) nodes. Key advantage over segment tree: 4x simpler code, better cache performance.
// 1D Fenwick Tree (1-indexed)
class BIT {
constructor(n) { this.n = n; this.tree = new Array(n + 1).fill(0); }
update(i, delta) {
for (; i <= this.n; i += i & (-i)) this.tree[i] += delta;
}
query(i) { // prefix sum [1..i]
let s = 0;
for (; i > 0; i -= i & (-i)) s += this.tree[i];
return s;
}
rangeQuery(l, r) { return this.query(r) - this.query(l - 1); }
// Point query (when using BIT as difference array):
// update(l, +1), update(r+1, -1) → query(i) gives range add value at i
}
// 2D Fenwick Tree
class BIT2D {
constructor(m, n) { this.m = m; this.n = n; this.t = Array.from({length:m+1},()=>new Array(n+1).fill(0)); }
update(r, c, v) {
for (let i = r; i <= this.m; i += i & (-i))
for (let j = c; j <= this.n; j += j & (-j))
this.t[i][j] += v;
}
query(r, c) {
let s = 0;
for (let i = r; i > 0; i -= i & (-i))
for (let j = c; j > 0; j -= j & (-j))
s += this.t[i][j];
return s;
}
rangeQuery(r1, c1, r2, c2) {
return this.query(r2,c2) - this.query(r1-1,c2) - this.query(r2,c1-1) + this.query(r1-1,c1-1);
}
}- BIT: simpler code (5 lines each), prefix queries only, requires invertible ops (sum/XOR, not max/min without modification)
- Segment Tree: any range query, range update, arbitrary merge functions
- For prefix sum + point update: always BIT
- For range max/min or range update: segment tree
Lowbit trick: i & (-i) isolates the lowest set bit. This is the key to BIT's structure.
Order-statistic BIT: combine coordinate compression + BIT to count elements in value ranges in O(log n) — core technique for merge sort order statistics and inversions.