Fenwick Tree (Binary Indexed Tree)
Definition
A Fenwick Tree is a clever data structure that does exactly what a Segment Tree does (Prefix Sums and Updates) but uses less memory and is easier to code. It relies heavily on binary bit manipulation.
How it Works
Unlike a standard array where index i holds value i, in a Fenwick Tree, index i holds the sum of a specific range determined by the Least Significant Bit (LSB) of i. It allows you to jump through the array in powers of 2 to calculate sums.
Real-World Analogy:
Imagine a Bucket System for collecting coins.
- Bucket 1 holds coins from day 1.
- Bucket 2 holds coins from day 1-2.
- Bucket 4 holds coins from day 1-4.
To find the total for 13 days, you don’t add 13 buckets. You grab the “Day 1-8” bucket, the “Day 9-12” bucket, and the “Day 13” bucket. Just 3 steps!
Code Example
PythonJavaCC++
# Update BIT (Fenwick Tree)
def update(BIT, n, i, val):
i += 1 # convert to 1-based index
while i 0:
s += BIT[i]
i -= i & (-i) # move to parent
return s
arr = [1, 2, 3, 4, 5]
n = len(arr)
BIT = [0] * (n + 1)
# Build Fenwick Tree
for i in range(n):
update(BIT, n, i, arr[i])
print("Sum of first 3 elements:", query(BIT, 2)) # 6
class FenwickTree {
int[] BIT;
int n;
FenwickTree(int n) {
this.n = n;
BIT = new int[n + 1];
}
// Update BIT
void update(int i, int val) {
i = i + 1;
while (i 0) {
sum += BIT[i];
i -= i & (-i);
}
return sum;
}
public static void main(String[] args) {
int arr[] = {1,2,3,4,5};
int n = arr.length;
FenwickTree ft = new FenwickTree(n);
for (int i = 0; i < n; i++)
ft.update(i, arr[i]);
System.out.println("Sum of first 3 elements: " + ft.query(2));
}
}
#include <stdio.h>
void update(int BIT[], int n, int i, int val) {
i = i + 1;
while (i 0) {
sum += BIT[i];
i -= i & (-i);
}
return sum;
}
int main() {
int arr[] = {1,2,3,4,5};
int n = 5;
int BIT[6] = {0};
for (int i = 0; i < n; i++)
update(BIT, n, i, arr[i]);
printf("Sum of first 3 elements: %d\n", query(BIT, 2));
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
class FenwickTree {
public:
vector<int> BIT;
int n;
FenwickTree(int n) {
this->n = n;
BIT.resize(n + 1, 0);
}
// Update BIT
void update(int i, int val) {
i = i + 1;
while (i 0) {
sum += BIT[i];
i -= i & (-i);
}
return sum;
}
};
int main() {
int arr[] = {1,2,3,4,5};
int n = 5;
FenwickTree ft(n);
for (int i = 0; i < n; i++)
ft.update(i, arr[i]);
cout << "Sum of first 3 elements: "
<< ft.query(2) << endl;
return 0;
}
Complexity Analysis
- Time Complexity:
- Update: O(log n)
- Query: O(log n)
- Space Complexity: O(n) (Uses same space as the input array, unlike Segment Tree).
Use Cases
- Cumulative Frequencies: Often used in data compression algorithms.
- Counting Inversions: Used to measure how “unsorted” an array is.
- Gaming Leaderboards: Calculating ranks dynamically.