Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About A Fenwick tree (Binary Indexed Tree / BIT) is a compact array-based data structure that supports prefix sums and point updates in O(log n)
A Fenwick tree (Binary Indexed Tree / BIT) is a compact array-based data structure that supports prefix sums and point updates in O(log n).
Each index i owns responsibility for the range (i − lowbit(i), i], and the lowbit trick makes both queries and updates a short O(log n) walk through these ranges.
It uses O(n) memory with a tiny constant.
How It Works
Fenwick relies on `lowbit(i) = i & −i`.
bit[i] stores the sum of the range (i − lowbit(i), i].
To build, add each arr[i] to bit[i] and then propagate to every ancestor j = i + lowbit(i) while j ≤ n.
A prefix sum to index p walks `while p > 0: sum += bit[p]; p -= lowbit(p)`.
A point update walks `while i <= n: bit[i] += delta; i += lowbit(i)`.
A range sum is prefix(r) − prefix(l−1).
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Build | O(n) | O(n) |
| Prefix sum | O(log n) | O(1) |
| Point update | O(log n) | O(1) |
| Range sum | O(log n) | O(1) |
| Memory | n + 1 array slots | O(n) |
Best Use Cases
- Range sum / range frequency queries with point updates
- Counting inversions (sweep the array, add at index, query prefix)
- K-th order statistics with a Fenwick of counts (binary search on prefix)
- Bit-level interval arithmetic and offline query problems
- Anything where a segment tree would work but a smaller constant matters
Worked Example
Build and query prefix(6) and range(2,6) on [3, 2, -1, 6, 5, 4, -3, 7]
Input: 1-indexed data = [3, 2, -1, 6, 5, 4, -3, 7]; prefix target 6; range (2,6)- 1 Build: each bit[i] accumulates arr over the range (i − lowbit(i), i].
- 2 bit[4] covers arr[1..4] = 3+2−1+6 = 10; bit[6] covers arr[5..6] = 5+4 = 9.
- 3 Prefix sum to 6 = bit[6] + bit[4] = 9 + 10 = 19 — a walk of O(log n) nodes.
- 4 Range sum (2,6) = prefix(6) − prefix(1) = 19 − 3 = 16.
- 5 Point update adds delta to bit[i] and every ancestor j = i + lowbit(i), also O(log n).
Pseudocode
function add(i, delta): # 1-indexed
while i <= n:
bit[i] += delta
i += i & -i
build(arr):
bit = zeros(n+1)
for i in 1..n: add(i, arr[i]) function prefix(i):
sum = 0
while i > 0:
sum += bit[i]
i -= i & -i
return sum
rangeSum(l, r) = prefix(r) - prefix(l - 1) Build
bit[i] stores a sum of the range ending at i — prefix sums and updates both run in O(log n).