Range Sum Query

Fenwick Tree is a data structure made for getting range sum query from data that is open for updating.


There is data A:

Index	0	1	2	3
Value	2	1	0	4

Update and Get Range Sum quickly!!

First Data Structure

We can get O(1) for updating the value from the certain index in our data.

A[2] = 5;

Index	0	1	2	3
Value	2	1	5	4

But we'll have O(N) for getting the range sum query.
RSQ(1,3) means A[1] + A[2] + A[3]
So, RSQ(1,3) = 1 + 5 + 4 = 10

Second Data Structure

Keep the cumulative frequency in each index.
It means that :
A[0] = A[0];
A[1] = A[0] + A[1];
A[2] = A[0] + A[1] + A[2];
A[3] = A[0] + A[1] + A[2] + A[3];

Index	0	1	2	3
Value	2	1	5	4
Cumulative	2	3	8	12

We can get O(1) for RSQ.

RSQ(1,3) = A[3] - A[0];
or RSQ(a,b) = A[b] - A[a-1];

But we'll have O(N) for updating data.
If we want to update a data A[x], we need to change the value from index x until N-1. Why? Because we are keeping the cumulative frequencies.

Third Data Structure - Fenwick Tree

This data structure keeps the cumulative value in a unique way.
It use Least Significant Bit to define the responsibility of each index. What kind of responsibility?
If we look at the Second Data Structure, each index X has responsibility for index 1 until X.
In Fenwick Tree we are going to cut that responsibility.
So, each index will not take responsibility for index 1 until X but only from it's least significant bit.

Look at the picture.
At index 1 we save the value 3 which is A[0] + A[1].
Why? Because we can get A[1] value by FT[1]-FT[0].

Not clear enough? Let's see on index 3. We save value 12.
How come?
12 is the value taken from FT[1] + FT[2] + A[3]
We can get value A[3] from FT[3] - FT[2] - FT[1].

That's the idea. Get it?

Now, how can we know which one needed to substract the value in FT?
It's using bitmask. Find out in the next post. :)