Fenwick Tree (Binary Indexed Tree)
Fenwick Tree (Binary Indexed Tree)¶
Overview¶
Fenwick Tree (BIT: Binary Indexed Tree) is a data structure that processes range sum queries and point updates in O(log n) time. It is simpler to implement and more memory efficient than a segment tree.
Table of Contents¶
1. Fenwick Tree Concept¶
1.1 Structure¶
Fenwick Tree: 1-indexed array based
Key idea: The range that element i is responsible for
is determined by the lowest bit (lowbit) of i
lowbit(i) = i & (-i)
Example (n=8):
Index: 1 2 3 4 5 6 7 8
lowbit: 1 2 1 4 1 2 1 8
Range: [1,1][1,2][3,3][1,4][5,5][5,6][7,7][1,8]
tree[1] = arr[1]
tree[2] = arr[1] + arr[2]
tree[3] = arr[3]
tree[4] = arr[1] + arr[2] + arr[3] + arr[4]
tree[5] = arr[5]
tree[6] = arr[5] + arr[6]
tree[7] = arr[7]
tree[8] = arr[1] + ... + arr[8]
1.2 Lowbit Visualization¶
When representing index in binary:
1 = 0001 β lowbit = 1 β tree[1] = A[1]
2 = 0010 β lowbit = 2 β tree[2] = A[1..2]
3 = 0011 β lowbit = 1 β tree[3] = A[3]
4 = 0100 β lowbit = 4 β tree[4] = A[1..4]
5 = 0101 β lowbit = 1 β tree[5] = A[5]
6 = 0110 β lowbit = 2 β tree[6] = A[5..6]
7 = 0111 β lowbit = 1 β tree[7] = A[7]
8 = 1000 β lowbit = 8 β tree[8] = A[1..8]
Pattern:
- Odd indices: lowbit = 1 (only itself)
- Powers of 2: lowbit = index (from 1 to itself)
1.3 Time/Space Complexity¶
βββββββββββββββββββ¬ββββββββββββββ¬ββββββββββββββ
β Operation β Time β Description β
βββββββββββββββββββΌββββββββββββββΌββββββββββββββ€
β Build β O(n) β or O(nlogn) β
β Point update β O(log n) β Value changeβ
β Prefix sum β O(log n) β [1, i] sum β
β Range sum β O(log n) β [l, r] sum β
βββββββββββββββββββ΄ββββββββββββββ΄ββββββββββββββ
Space: O(n) - 1/2 to 1/4 of segment tree
2. Basic Implementation¶
2.1 Python Implementation¶
class FenwickTree:
def __init__(self, n):
"""Fenwick tree of size n (1-indexed)"""
self.n = n
self.tree = [0] * (n + 1)
def update(self, i, delta):
"""arr[i] += delta"""
while i <= self.n:
self.tree[i] += delta
i += i & (-i) # Move to next node
def prefix_sum(self, i):
"""arr[1] + arr[2] + ... + arr[i]"""
total = 0
while i > 0:
total += self.tree[i]
i -= i & (-i) # Move to previous node
return total
def range_sum(self, l, r):
"""arr[l] + arr[l+1] + ... + arr[r]"""
return self.prefix_sum(r) - self.prefix_sum(l - 1)
# Usage example
n = 8
bit = FenwickTree(n)
# Build array [0, 1, 2, 3, 4, 5, 6, 7, 8] (1-indexed)
for i in range(1, n + 1):
bit.update(i, i)
print(bit.prefix_sum(4)) # 10 (1+2+3+4)
print(bit.range_sum(2, 5)) # 14 (2+3+4+5)
bit.update(3, 5) # arr[3] += 5
print(bit.range_sum(2, 5)) # 19 (2+8+4+5)
2.2 Initialize from Array¶
class FenwickTreeFromArray:
def __init__(self, arr):
"""Build Fenwick tree from array - O(n)"""
self.n = len(arr)
self.tree = [0] * (self.n + 1)
# O(n) initialization
for i in range(1, self.n + 1):
self.tree[i] += arr[i - 1] # arr is 0-indexed
j = i + (i & (-i))
if j <= self.n:
self.tree[j] += self.tree[i]
def update(self, i, delta):
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def prefix_sum(self, i):
total = 0
while i > 0:
total += self.tree[i]
i -= i & (-i)
return total
def range_sum(self, l, r):
return self.prefix_sum(r) - self.prefix_sum(l - 1)
# Usage example
arr = [1, 2, 3, 4, 5, 6, 7, 8]
bit = FenwickTreeFromArray(arr)
print(bit.range_sum(1, 4)) # 10
2.3 C++ Implementation¶
#include <vector>
using namespace std;
class FenwickTree {
private:
vector<long long> tree;
int n;
public:
FenwickTree(int n) : n(n), tree(n + 1, 0) {}
FenwickTree(const vector<int>& arr) : n(arr.size()), tree(arr.size() + 1, 0) {
for (int i = 1; i <= n; i++) {
tree[i] += arr[i - 1];
int j = i + (i & (-i));
if (j <= n) tree[j] += tree[i];
}
}
void update(int i, long long delta) {
while (i <= n) {
tree[i] += delta;
i += i & (-i);
}
}
long long prefixSum(int i) {
long long total = 0;
while (i > 0) {
total += tree[i];
i -= i & (-i);
}
return total;
}
long long rangeSum(int l, int r) {
return prefixSum(r) - prefixSum(l - 1);
}
};
3. Operations¶
3.1 Update Process Visualization¶
update(3, 5): arr[3] += 5
Index movement: 3 β 4 β 8 (β 16 exceeds n)
3 = 0011 β tree[3] += 5
0011 + 0001 = 0100
4 = 0100 β tree[4] += 5
0100 + 0100 = 1000
8 = 1000 β tree[8] += 5
1000 + 1000 = 10000 (> n, stop)
Affected nodes: tree[3], tree[4], tree[8]
3.2 Query Process Visualization¶
prefix_sum(7): arr[1] + ... + arr[7]
Index movement: 7 β 6 β 4 β 0
7 = 0111 β total += tree[7] (arr[7])
0111 - 0001 = 0110
6 = 0110 β total += tree[6] (arr[5..6])
0110 - 0010 = 0100
4 = 0100 β total += tree[4] (arr[1..4])
0100 - 0100 = 0000
0 = 0000 (stop)
Result: tree[7] + tree[6] + tree[4] = arr[1..7]
3.3 Point Query¶
class FenwickTreePointQuery:
"""Range update + point query"""
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def range_update(self, l, r, delta):
"""arr[l..r] += delta"""
self._update(l, delta)
if r + 1 <= self.n:
self._update(r + 1, -delta)
def _update(self, i, delta):
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def point_query(self, i):
"""arr[i] value"""
total = 0
while i > 0:
total += self.tree[i]
i -= i & (-i)
return total
# Example
bit = FenwickTreePointQuery(8)
bit.range_update(2, 5, 3) # arr[2..5] += 3
print(bit.point_query(3)) # 3
print(bit.point_query(6)) # 0
3.4 Finding K-th Element¶
def find_kth(bit, k):
"""
Find minimum index where prefix sum >= k
(bit[i] = 1 if element exists)
Time: O(log n)
"""
n = bit.n
pos = 0
total = 0
# Search from highest bit
log_n = n.bit_length()
for i in range(log_n - 1, -1, -1):
next_pos = pos + (1 << i)
if next_pos <= n and total + bit.tree[next_pos] < k:
total += bit.tree[next_pos]
pos = next_pos
return pos + 1 # Index of k-th element
# Example: dynamic k-th element
class DynamicKth:
def __init__(self, max_val):
self.bit = FenwickTree(max_val)
def add(self, x):
"""Add element x"""
self.bit.update(x, 1)
def remove(self, x):
"""Remove element x"""
self.bit.update(x, -1)
def kth(self, k):
"""K-th smallest element"""
return find_kth(self.bit, k)
def count_less(self, x):
"""Count of elements less than x"""
return self.bit.prefix_sum(x - 1)
# Usage
dk = DynamicKth(100)
dk.add(5)
dk.add(10)
dk.add(3)
dk.add(7)
print(dk.kth(2)) # 5 (sorted: 3, 5, 7, 10)
print(dk.count_less(7)) # 2 (3, 5)
4. Applications¶
4.1 Inversion Count¶
def count_inversions(arr):
"""
Inversion pairs: count of (i, j) where i < j and arr[i] > arr[j]
Time: O(n log n)
"""
# Coordinate compression
sorted_arr = sorted(set(arr))
rank = {v: i + 1 for i, v in enumerate(sorted_arr)}
max_rank = len(sorted_arr)
bit = FenwickTree(max_rank)
count = 0
# Process from right to left
for val in reversed(arr):
r = rank[val]
# Count of values smaller than r (already processed = was on the right)
count += bit.prefix_sum(r - 1)
bit.update(r, 1)
return count
# Example
arr = [7, 5, 6, 4]
print(count_inversions(arr)) # 5: (7,5), (7,6), (7,4), (5,4), (6,4)
4.2 Range Update + Range Query¶
class FenwickTreeRURQ:
"""
Range Update, Range Query
Uses two BITs
"""
def __init__(self, n):
self.n = n
self.bit1 = [0] * (n + 2)
self.bit2 = [0] * (n + 2)
def _update(self, bit, i, delta):
while i <= self.n:
bit[i] += delta
i += i & (-i)
def _query(self, bit, i):
total = 0
while i > 0:
total += bit[i]
i -= i & (-i)
return total
def range_update(self, l, r, delta):
"""arr[l..r] += delta"""
self._update(self.bit1, l, delta)
self._update(self.bit1, r + 1, -delta)
self._update(self.bit2, l, delta * (l - 1))
self._update(self.bit2, r + 1, -delta * r)
def prefix_sum(self, i):
"""arr[1] + ... + arr[i]"""
return self._query(self.bit1, i) * i - self._query(self.bit2, i)
def range_sum(self, l, r):
"""arr[l] + ... + arr[r]"""
return self.prefix_sum(r) - self.prefix_sum(l - 1)
# Example
bit = FenwickTreeRURQ(8)
bit.range_update(2, 5, 3) # arr[2..5] += 3
print(bit.range_sum(1, 4)) # 9 (0+3+3+3)
print(bit.range_sum(3, 6)) # 12 (3+3+3+3)
4.3 Offline Query Processing¶
def offline_range_sum(arr, queries):
"""
Query: (l, r, type)
type 1: arr[l] += r
type 2: return sum of arr[l..r]
"""
n = len(arr)
bit = FenwickTreeFromArray(arr)
results = []
for query in queries:
if query[0] == 1:
_, idx, val = query
bit.update(idx, val)
else:
_, l, r = query
results.append(bit.range_sum(l, r))
return results
5. 2D Fenwick Tree¶
5.1 Implementation¶
class FenwickTree2D:
def __init__(self, rows, cols):
self.rows = rows
self.cols = cols
self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]
def update(self, x, y, delta):
"""arr[x][y] += delta"""
i = x
while i <= self.rows:
j = y
while j <= self.cols:
self.tree[i][j] += delta
j += j & (-j)
i += i & (-i)
def prefix_sum(self, x, y):
"""Sum of arr[1..x][1..y]"""
total = 0
i = x
while i > 0:
j = y
while j > 0:
total += self.tree[i][j]
j -= j & (-j)
i -= i & (-i)
return total
def range_sum(self, x1, y1, x2, y2):
"""Sum of arr[x1..x2][y1..y2]"""
return (self.prefix_sum(x2, y2)
- self.prefix_sum(x1 - 1, y2)
- self.prefix_sum(x2, y1 - 1)
+ self.prefix_sum(x1 - 1, y1 - 1))
# Example
bit2d = FenwickTree2D(4, 4)
matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]
# Initialize
for i in range(4):
for j in range(4):
bit2d.update(i + 1, j + 1, matrix[i][j])
print(bit2d.range_sum(2, 2, 3, 3)) # 34 (6+7+10+11)
5.2 C++ 2D Implementation¶
class FenwickTree2D {
private:
vector<vector<long long>> tree;
int rows, cols;
public:
FenwickTree2D(int r, int c) : rows(r), cols(c) {
tree.assign(r + 1, vector<long long>(c + 1, 0));
}
void update(int x, int y, long long delta) {
for (int i = x; i <= rows; i += i & (-i)) {
for (int j = y; j <= cols; j += j & (-j)) {
tree[i][j] += delta;
}
}
}
long long prefixSum(int x, int y) {
long long total = 0;
for (int i = x; i > 0; i -= i & (-i)) {
for (int j = y; j > 0; j -= j & (-j)) {
total += tree[i][j];
}
}
return total;
}
long long rangeSum(int x1, int y1, int x2, int y2) {
return prefixSum(x2, y2) - prefixSum(x1 - 1, y2)
- prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
}
};
6. Practice Problems¶
Recommended Problems¶
| Difficulty | Problem | Platform | Type |
|---|---|---|---|
| βββ | Range Sum Query | BOJ | Basic |
| βββ | Range Sum Query - Mutable | LeetCode | Basic |
| βββ | Bubble Sort | BOJ | Inversion |
| ββββ | Count of Smaller Numbers | LeetCode | Inversion |
| ββββ | Rectangle Sum | BOJ | 2D BIT |
Segment Tree vs Fenwick Tree¶
ββββββββββββββββββ¬βββββββββββββββ¬βββββββββββββββ
β Criterion β Segment Tree β Fenwick Tree β
ββββββββββββββββββΌβββββββββββββββΌβββββββββββββββ€
β Space β O(4n) β O(n) β
β Implementation β Medium β Simple β β
β Constant factorβ Large β Small β β
β Point query β β β β β
β Range query β β β β β
β Range update β Needs Lazy β Needs 2 BITs β
β Versatility β High β β Low (sum only)β
β Min/Max β β β β β
ββββββββββββββββββ΄βββββββββββββββ΄βββββββββββββββ
Conclusion:
- Only need range sum β Fenwick Tree
- Min/Max/Complex operations β Segment Tree
Next Steps¶
- 25_Network_Flow.md - Network Flow