The Simple Implementation of Binary Index Tree (BIT or Fenwick Tree)

Introduction to Binary Index Tree or Fenwick Tree

Binary Index Tree (BIT) aka Fenwick Tree is a simple data structure that has O(LogN) complexity in updating element in a list and querying the accumulate sum or sum between a given range.

You can achieve O(1) constant complexity in calculating the accumulate sum or interval sum using a prefix sum array with O(N) space. Or you can store the original numbers and enjoy the O(1) update.

The Binary Index Search is simpler to implement than a Segment Tree (which we will cover in a separate post C++ Implementation of Segment Tree). You can pass an array/vector into the BIT constructor or, alternative you can specify the maximum number of elements in the BIT data structure. Usually, we pad a zero in the begining so that when we compute the range sum between two indices, we don’t need to worry about index being out of range e.g. -1.

C++ Binary Index Tree Implementation (Fenwick Tree)

The Binary Index Tree implementation in C++:

class BIT {
private:
    vector<int> data;
    
public:
    BIT(vector<int> nums) {
        data.resize(nums.size() + 1);
        for (int i = 0; i < nums.size(); ++ i) {
            add(i, nums[i]);
        }
    }
    
    BIT(int n) {
        data.resize(n + 1);
    }
    
    // add the value val to index i
    void add(int i, int val) {
        ++ i;
        while (i < data.size()) {
            data[i] += val;
            i += (i & (-i));
        }
    }
    
    // get the prefix sum from 0 to i
    int sum(int i) {
        ++ i;
        int v = 0;
        while (i) {
            v += data[i];
            i -= (i & (-i));
        }
        return v;
    }

    // get the range sum between [i, j]
    int queryRange(int i, int j) {
        return sum(j) - sum(i - 1);
    }
};

Here is another implementation:

class BIT {
private:
    vector<int> tree;
    int n;

public:
    BIT(int _n) : n(_n), tree(_n + 1) {}

    static constexpr int lowbit(int x) {
        return x & (-x);
    }

    void update(int x, int d) {
        while (x <= n) {
            tree[x] += d;
            x += lowbit(x);
        }
    }

    int query(int x) const {
        int ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
};

Java Binary Index Tree Implementation (Fenwick Tree)

The Java Implementation of Fenwick Tree is quite similar to C++ version.

class BinaryIndexTree {
    int[] counts;
    int size;

    public BinaryIndexTree(int n) {
        size = n + 1;
        counts = new int[size];
    }

    public BinaryIndexTree(int[] counts) {
        size = counts.length() + 1;
        this.counts = counts;
        for (int i = 0; i < counts.length(); ++ i) {
            add(i, counts[i]);
        }
    }

    // add val to nums[i] and update the tree.
    public void add(int i, int val) {
        ++i;
        while (i < size) {
            counts[i] += val;
            i += Integer.lowestOneBit(i);
        }
    }

    // get the prefix/accumulate sum from [0, i]
    public int sum(int i) {
        ++i;
        int ans = 0;
        while (i &t; 0) {
            ans += counts[i];
            i -= Integer.lowestOneBit(i);
        }
        return ans;
    }

    // get the range sum between [i, j]
    public int queryRange(int i, int j) {
        return sum(j) - sum(i - 1);
    }
}

The Fenwick Tree allows you to mutate the list and compute the range sum in both O(logN) – which is a good balance if you need to update and query many many times.

–EOF (The Ultimate Computing & Technology Blog) —