Fenwick Tree (BIT)#
Metadata
Level: Intermediate · Difficulty: 3.0 · Complexity: O(log n) per operation
A Fenwick tree (or Binary Indexed Tree) maintains prefix sums of an array while allowing point updates and range queries, both in O(log n). It is the ideal structure when the array changes and we need range sums many times.
![Each cell T[i] covers a block whose size is its lowest set bit](media/fenwick-tree.svg)
T[i] stores the sum of a block ending at position
i whose size is the lowest set bit of i.Idea#
A prefix-sum array answers queries in O(1), but changing a single element forces an O(n) rebuild of the prefixes. A Fenwick tree splits the information into blocks of different sizes so that both updating and querying touch only O(log n) blocks.
Internally the indices are 1-based (the user's 0-based position p lives at internal
position p + 1). Cell T[i] stores the sum of the half-open range (i − lowbit(i), i],
where lowbit(i) is the lowest set bit of i:
lowbit(i) = i & -i. In two's complement,-iflips every bit and adds 1, soi & -ikeeps only the lowest set bit. That value is both the size of the block covered byT[i]and the jump we take while walking the tree.- Odd indices (
lowbit = 1) cover a single element; powers of two cover a large block (T[8]covers all 8 positions).
update and query walk the tree in opposite directions:
update(index, delta)walks up: from the position, repeatindex += index & -index. Each jump lands on the next cell whose block contains that position, so every affected block is updated (at most O(log n)).query(index)walks down: repeatindex -= index & -index. Removing the lowest set bit jumps to the block just before it; the visited blocks are disjoint and tile exactly[0, index). Since each step clears one bit, there are at most O(log n) steps.
Queries are half-open: query(index) returns the sum of [0, index), and a range
sum is the difference of two prefixes: query_range(l, r) = query(r) − query(l).
Example#
Start from an array of 5 zeros and apply the test operations: update(0, 3) then
update(2, 5). The logical array becomes a = [3, 0, 5, 0, 0].
After both updates the internal cells (1-based) hold:
| Cell | Covers (1-based positions) | Value |
|---|---|---|
T[1] |
{1} |
3 |
T[2] |
{1, 2} |
3 |
T[3] |
{3} |
5 |
T[4] |
{1, 2, 3, 4} |
8 |
T[5] |
{5} |
0 |
Now query(3) (sum of [0, 3)) walks down from index = 3: add T[3] = 5, jump to
3 − 1 = 2, add T[2] = 3, jump to 0. Total 5 + 3 = 8. Note that the blocks (2, 3]
and (0, 2] cover exactly the first three positions without overlapping.
Likewise query(5) adds T[5] = 0 and T[4] = 8, giving 8. Hence
query_range(0, 3) = 8 and query_range(0, 5) = 8, the example's expected output.
Code#
/**
* Fenwick Tree (Binary Indexed Tree).
*
* A structure for prefix sums with point updates: it stores an array and
* answers range-sum queries and single-element updates, both in O(log n). Ideal
* when the array keeps changing and range sums are needed many times.
*
* The public API is 0-based, but the tree is stored 1-based: cell `i` (1..n)
* holds the sum of the half-open block (i - lowbit(i), i], where lowbit is the
* lowest set bit of `i`. That block size is what lets both operations move in
* O(log n) steps.
*
* FenwickTree(n) build an empty tree of n zeros O(n)
* update(index, delta) add `delta` at position `index` O(log n)
* query(index) -> prefix sum of [0, index) O(log n)
* query_range(l, r) -> sum of [l, r) O(log n)
*/
#include <vector>
using namespace std;
struct FenwickTree {
int n;
vector<int> tree; // 1-based cell i (stored at tree[i-1]) covers (i-lowbit(i), i]
// Create a Fenwick tree of `n` elements, all zero.
FenwickTree(int n) : n(n), tree(n) {}
// Add `delta` to the element at `index` (0-based).
void update(int index, int delta) {
// `index++` converts to 1-based, then we walk UP: `index & -index`
// isolates the lowest set bit, and adding it jumps to the next cell
// whose block also contains this position (at most O(log n) cells).
for (index++; index <= n; index += index & -index)
tree[index - 1] += delta;
}
// Return the prefix sum of [0, index).
int query(int index) {
// A 0-based exclusive bound equals the 1-based element count, so no +1.
// Walk DOWN: subtracting the lowest set bit jumps to the block just
// before this one; the visited blocks tile [0, index) with no overlap.
int acc = 0;
for (; index > 0; index -= index & -index)
acc += tree[index - 1];
return acc;
}
// Return the sum of the half-open range [l, r).
int query_range(int l, int r) { return query(r) - query(l); }
};
#include <vector>
using namespace std;
struct FenwickTree {
int n;
vector<int> tree;
FenwickTree(int n) : n(n), tree(n) {}
void update(int index, int delta) {
for (index++; index <= n; index += index & -index)
tree[index - 1] += delta;
}
int query(int index) {
int acc = 0;
for (; index > 0; index -= index & -index)
acc += tree[index - 1];
return acc;
}
int query_range(int l, int r) { return query(r) - query(l); }
};
#include <vector>
using namespace std;
struct FenwickTree {
int n;
vector<int> tree;
FenwickTree(int n) : n(n), tree(n) {}
void update(int index, int delta) {
for (index++; index <= n; index += index & -index)
tree[index - 1] += delta;
}
int query(int index) {
int acc = 0;
for (; index > 0; index -= index & -index)
acc += tree[index - 1];
return acc;
}
int query_range(int l, int r) { return query(r) - query(l); }
};
"""Fenwick Tree (Binary Indexed Tree).
A structure for **prefix sums with point updates**: it stores an array and
answers range-sum queries and single-element updates, both in O(log n). Ideal
when the array keeps changing and range sums are needed many times.
The public API is 0-based, but the tree is stored 1-based: cell ``i`` (1..n)
holds the sum of the half-open block ``(i - lowbit(i), i]``, where ``lowbit`` is
the lowest set bit of ``i``. That block size is what lets both operations move
in O(log n) steps.
build: O(n) · update: O(log n) · query: O(log n) · space: O(n)
"""
class FenwickTree:
def __init__(self, n: int) -> None:
"""Create a Fenwick tree of ``n`` elements, all zero.
Args:
n (int): number of elements.
"""
self.n: int = n
self.tree: list[int] = [0] * n
def update(self, index: int, delta: int) -> None:
"""Add ``delta`` to the element at ``index``.
Args:
index (int): 0-based position to update.
delta (int): amount to add.
"""
index += 1 # switch to 1-based indexing
while index <= self.n:
self.tree[index - 1] += delta
# `index & -index` isolates the lowest set bit; adding it walks UP
# to the next cell whose block also contains this position.
index += index & -index
def query(self, index: int) -> int:
"""Prefix sum of the half-open range ``[0, index)``.
Args:
index (int): exclusive upper bound.
Returns:
int: sum of the elements in ``[0, index)``.
"""
# A 0-based exclusive bound equals the 1-based element count, so no +1.
acc: int = 0
while index > 0:
acc += self.tree[index - 1]
# Subtract the lowest set bit to walk DOWN to the previous block;
# the visited blocks tile [0, index) with no overlap.
index -= index & -index
return acc
def query_range(self, l: int, r: int) -> int:
"""Sum of the half-open range ``[l, r)``.
Args:
l (int): inclusive lower bound.
r (int): exclusive upper bound.
Returns:
int: sum of the elements in ``[l, r)``.
"""
return self.query(r) - self.query(l)
class FenwickTree:
def __init__(self, n: int) -> None:
self.n: int = n
self.tree: list[int] = [0] * n
def update(self, index: int, delta: int) -> None:
index += 1
while index <= self.n:
self.tree[index - 1] += delta
index += index & -index
def query(self, index: int) -> int:
acc: int = 0
while index > 0:
acc += self.tree[index - 1]
index -= index & -index
return acc
def query_range(self, l: int, r: int) -> int:
return self.query(r) - self.query(l)
class FenwickTree:
def __init__(self, e):
self.n = e
self.tree = [0] * e
def update(self, c, b):
c += 1
while c <= self.n:
self.tree[c - 1] += b
c += c & -c
def query(self, c):
a = 0
while c > 0:
a += self.tree[c - 1]
c -= c & -c
return a
def query_range(self, d, f):
return self.query(f) - self.query(d)
Complexity#
| Operation | Complexity | Reason |
|---|---|---|
| Build | O(n) | allocate the vector of n zeros |
update |
O(log n) | walks up jumping block by block, one per bit |
query |
O(log n) | walks down adding disjoint blocks, one per set bit |
| Memory | O(n) | one cell per element |
When to use it#
- Changing array + many range sums → Fenwick tree. This is where it shines: both operations in O(log n) with very little code and a small constant.
- Static array (never changes) → a plain precomputed prefix-sum array answers in O(1) and is simpler; you do not need a Fenwick tree.
- More general operations (range max/min, range assignment, lower-bound searches) → a segment tree is more flexible at the cost of more code. The Fenwick tree is its lightweight version for sums.
Trick
For range updates with point queries, apply the Fenwick tree on the difference
array: update(l, +v) and update(r, −v) add v to the whole [l, r).
Common pitfalls#
- Mixing up 0-based (public interface) and 1-based (internal). The
index++at the start ofupdateperforms that conversion; do not duplicate it. - Forgetting that queries are half-open:
query_range(l, r)excludesr. For the inclusive sum of[l, r]usequery_range(l, r + 1). - Sizing the tree wrong: the loop in
updatechecksindex <= n, so the vector must have room for then1-based positions.
Practice#
| Name | Difficulty | Link |
|---|---|---|
| fenwick | 4.0 | Kattis |
| supercomputer | 2.7 | Kattis |