Fenwick Tree (Binary Indexed Tree / BIT) Code Implementations
Production-ready Fenwick Tree (Binary Indexed Tree / BIT) data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.
Study Fenwick Tree (Binary Indexed Tree / BIT) Guide ยท Launch Visualizer
CPP Implementation
#include <vector>
// Fenwick Tree or Binary Indexed Tree
class FenwickTree {
private:
std::vector<int> BITree; // Binary Indexed Tree
public:
// Constructor to initialize the tree with a given size
FenwickTree(int size) : BITree(size + 1, 0) {}
// Function to get sum of the range [1, index]
int getSum(int index) {
int sum = 0;
index = index + 1;
while (index > 0) {
sum += BITree[index];
index -= index & (-index);
}
return sum;
}
// Function to update a value in Binary Indexed Tree
void update(int index, int val) {
index = index + 1;
while (index <= BITree.size()) {
BITree[index] += val;
index += index & (-index);
}
}
// Function to get the size of the tree
int size() {
return BITree.size() - 1;
}
// Function to check if the tree is empty
bool isEmpty() {
return BITree.size() == 1;
}
};