Binary Indexed Tree (BIT) / Fenwick Tree

 Source : 

1. Link 1

2. Link 2

3. Link 3

Code : 

Application : 

[Adv. over segment tree - it takes O(n) space and easy to code but time complexity is equal.]

1. Point update & range query : Update a point and do query in a range. Query can be done if the operations are associative & commutative (+, |, &, ^, min, max etc). 

- rangeUpdate(l, r, x) : where l = r.

- rangeQuery(l, r): Here we will calculate query(0, r) and query(0, l-1), in case of min/max we can't do query like this, we can do only query(0, r).

2. Range update & point query : Make two Tree initially zero. Then rangeUpdate(l, r, x) & for point query rangeQuery(l, r) where l = r.

3. Range update & Range query : rangeUpdate(l, r, x) & rangeQuery(l, r).
For more see this.

 Code :

4. Finding Sum in 2D Array (n x m) : Update(x, y, value) & Query(x, y) will do the work.

void update(int x, int y, ll value)

{

     while(x <= n) {

        int y1 = y;

        while(y1 <= m)  {

            Tree[x][y1] += value;

            y1 = y1 + (y1 & (-y1));            

        } 

        x = x + (x & (-x));

    } 

}

Query function will be same. 

Some Problems : 

1. DQUERY - D-query

2. Subsequences

3. MATSUM - Matrix Summation 

 

To be continued...