Binary Indexed Tree (Fenwick Tree)


What is a Binary Indexed Tree

Binary Indexed Tree is a data structure that can store array AA of length nn with following property

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

Why do we need it

Naive calculation of ff in the range [l,r][l,r] usually cost O(n)O(n). Imagine you have 10510^5 queries, each of them traverse through an array length 10510^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

BIT representation for an array length 8

(image taken from cp-algorithms.com)

In this example, let AA be the original array and BB be the BIT version of AA. Let ff be the sum function for the sake of simplicity.

Here is the process to calculate f(6)=A0+A1+A2+A3+A4+A5+A6f(6) = A_0 + A_1 + A_2 + A_3 + A_4 + A_5 + A_6

  1. Start with B6B_6, B6B_6 covers only A6A_6, we add B6B_6 the the final result
  2. Next, we want to go to the next uncovered range, which is B61=B5B_{6-1} = B_5, B5B_5 covers A[4,5]A[4,5], we add B5B_5 to the final result
  3. Next uncovered range, B41=B3B_{4-1} = B_3. B3B_3 covers A[0,3]A[0,3]. Add B3B_3 to the final result. We end here because we have covered the range A[0,6]A[0,6].

What if you want to calculate f(5)=A0+A1+A2+A3+A4+A5f(5) = A_0 + A_1 + A_2 + A_3 + A_4 + A_5

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

What if you want to calculate f(7)=A0+A1+A2+A3+A4+A5+A6+A7f(7) = A_0 + A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7

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

Definition of gg

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

In other words, if the least significant digit of ii in binary is 0, then g(i)=ig(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 gg using bitwise operator as follow

g(i)=i&(i+1)g(i) = i\&(i+1)

Example of gg

g(11)=g(10112)=10002=8g(11) = g(1011_2) = 1000_2 = 8

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

g(12)=g(11002)=11002=12g(14)=g(11102)=11102=14\begin{align*} g(12) = g(1100_2) = 1100_2 = 12 \\ g(14) = g(1110_2) = 1110_2 = 14 \end{align*}

It means B12,B14B_{12}, B_{14} will be respectively covering A12,A14A_{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

Made with love using Svelte, Three.js