Fenwick Tree

A fenwick tree is a compact data structure that allows to perform point/range queries as well as updates. 

Define low(i) to be the value of the rightmost 1 bit in the base2 representation of i. 

For example low(10) = 2 since 10 is 1010 in base 2 and the rightmost 1 has value 2. 

low(24) = 8 since 24 is 11000 in base 2. 

In most programming languages, we can find low(i) using i & -i

Let first assume we want to do range sum queries and point updates. 

A fenwick tree is an array B such that B[i] stores A[x] + A[x+1] … A[i] where x = i – low(i) + 1.

It is possible to prove that

  1. You can use the array B to construct the interval [1, i] for all i <= N
  2. The interval [1, i] can be broken down into at most logN disjoint intervals
  3. Every index is in at most logN intervals (at most logN values of B[i] cover i) 

In fact, we can construct the interval [1, i] by repeatedly subtracting low(i) from i to get to the next interval. 

As such the code for a Fenwick tree is very short and can be written as so: 

template <typename T>
struct Fenwick{
    int N;
    vector<T> bit;
    Fenwick(int n){
        N = n; bit.resize(N + 1);
    }
    void upd(int v, T val){//We want to update all intervals that contain v (there are at most logN)//It turns out adding low(v) will move you onto the next interval that contains v
        for(; v <= N; v += (v & -v)){
            bit[v] += val;
        }
    }
    T qry(int v){//We want to decompose [1, v] into logN intervals//Subtracting low(v) will result in us going to the next interval
        T res = 0; //res = sum of all values in [1, v]
        for(; v; v -= (v & -v)){
            res += bit[v];
        }
        return res;
    }
};

Extensions

Before we saw how to do point update and range query. Now what if we wanted to do range update and point query? 

Naively, this would take O(NlogN) worst case per update. However, since we only want point queries we can in fact store the difference array inside of our Fenwick Tree.

If we have array A, we store array Di=Ai-Ai-1. Observe that Ai is just equal to k=1iDk, which is just a prefix sum of D. Also note if we want to do a range update from l to r with value x, simply update Dlby +x and Dr+1by -x to maintain the difference array. Hence we have solved range update and point queries.

It is also possible to do both range update and range query, except now we need to maintain a prefix sum of the prefix sum of the difference array, which we can do with 2 Fenwick Trees. 

Practice: https://dmoj.ca/problem/ds1