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. :)

Snake Game HTML 5

Somedays ago my lecturer taught us to use HTML 5 canvas. He gave some code of snake and I updated it a little bit so that the snake won't die as it hit the border.

Check here for better view of the code

Team Queue Uva 540

Problem: Uva 540
I find that this problem is interesting. When we discuss about queue, it's not always strict queue rule that we have in mind. Sometimes people can just cut the line because they know someone in the line.

The idea of solving is using list of queue.

1. Each time an element comes, check each list member which is a queue.
2. If the queue.front() 's team is the same with the new element, just push it to the queue
3. else check other member of the list
4. if there is no element with the same team, create new queue in the back of the list

Here's my code.