Binary Indexed Tree (Fenwick Tree)

What is a Binary Indexed Tree

Binary Indexed Tree is a data structure that can store array $A$ of length $n$ with following property

• Calculates the value of function $f$ in the given range $[l, r]$ in $O(log(n))$ time. There are some restriction on which kind of function $f$ you can use, for example sum function works, but min/max function don’t.
• Updates the value of an element of $A$ in $O(log(n))$ time
• Requires only $O(n)$ spaces, which is the input spaces

Why do we need it

Naive calculation of $f$ in the range $[l,r]$ usually cost $O(n)$. Imagine you have $10^5$ queries, each of them traverse through an array length $10^5$, you would end up having 10 billions traversal and TLE.

How it works

Here is an example of a BIT representation for an array of 8 items

(image taken from cp-algorithms.com)

In this example, let $A$ be the original array and $B$ be the BIT version of $A$. Let $f$ be the sum function for the sake of simplicity.

Here is the process to calculate $f(6) = A_0 + A_1 + A_2 + A_3 + A_4 + A_5 + A_6$

1. Start with $B_6$, $B_6$ covers only $A_6$, we add $B_6$ the the final result
2. Next, we want to go to the next uncovered range, which is $B_{6-1} = B_5$, $B_5$ covers $A[4,5]$, we add $B_5$ to the final result
3. Next uncovered range, $B_{4-1} = B_3$. $B_3$ covers $A[0,3]$. Add $B_3$ to the final result. We end here because we have covered the range $A[0,6]$.

What if you want to calculate $f(5) = A_0 + A_1 + A_2 + A_3 + A_4 + A_5$

1. Start with $B_5$, $B_5$ covers $A[4,5]$, we add $B_5$ to the final result
2. Next, we want to go to the next uncovered range, which is $B_{4-1} = B_3$. $B_3$ covers $A[0,3]$. Add $B_3$ to the final result and we are done.

What if you want to calculate $f(7) = A_0 + A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7$

1. Start with $B_7$, Luckily enough, $B_7$ covers $A[0, 7]$ so we already got the answer, which is $B_7$

Definition of $g$

The computation of $g(i)$ is defined using the following simple operation: we replace all trailing 1 bits in the binary representation of $i$ with 0 bits.

In other words, if the least significant digit of $i$ in binary is 0, then $g(i)=i$. And otherwise the least significant digit is a 1, and we take this 1 and all other trailing 1s and flip them.

There exists a simple implementation of $g$ using bitwise operator as follow

Example of $g$

It means $B_{11}$ will be covering $A[8,11]$

It means $B_{12}, B_{14}$ will be respectively covering $A_{12}, A_{14}$ only

C++ implementation

BIT 1D

struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

BIT 2D

struct FenwickTree2D {
    vector<vector<int>> bit;
    int n, m;

    // init(...) { ... }

    int sum(int x, int y) {
        int ret = 0;
        for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
            for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
                ret += bit[i][j];
        return ret;
    }

    void add(int x, int y, int delta) {
        for (int i = x; i < n; i = i | (i + 1))
            for (int j = y; j < m; j = j | (j + 1))
                bit[i][j] += delta;
    }
};

Learn more

See this for more detailed explaination: https://cp-algorithms.com/data_structures/fenwick.html