AntInLoop

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;
    }
};