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. 

Recursive 4 - Get Gold part 2

previous post

You've learned about making one direction checking. From your current position, you can find out something in one block to the right. If you can't move anymore or you get the gold, you will return. That's what we're talking about in the previous post.

Now, I will continue about making more than one direction checking. How if we have a map that looks like this.

The Dog		Gold
	#	#
Gold	#	#

In this situation, we can get the gold by moving right or down. There are 2 alternatives. How do we make the dog to check both right and down?

 In the previous post you'll find code like this

if(j < 3)   // to check whether the current position is not bigger than the number of column

{

     if(array[j] == 1)  // to check whether the current position has the gold or not

         return 1;

     else 

         find_1(j+1);      // to move to the next position,  (j + 1) means move to the right.

}
We need to check not only the columns, but also the rows. So we need not only j  but also i to check the rows. We can start making the down checking by adding the parameter.

Change this bool find_1(int j){} into bool find_1(int i, int j){}
i for the rows
j for the columns

Then, change the array, from 1 dimension into 2 dimensions. From array[j] into array[i][j]
Wait, don't forget to change the calling of the method find_1. From find_1(j+1) into find(i, j+1)

Now we're getting into the answer of the question. To make the checking for both direction, you can just simply add another if block.

Column check:

if(j < 3)

{

     if(array[i][j] == 1)  

         return 1;

     else 

         find_1(i, j+1);  

}

Row check:

if(i < 3)

{

     if(array[i][j] == 1)  

         return 1;

     else 

         find_1(i+1,j);  

}

But there's a problem. 

1. It would only check the column. Because when the column check fails, it directly return 0 to the main. 

    Solution : use a variable to keep the status whether there is gold or not from the right.

2. If we have add a variable flag to solve the 1st problem, there's another problem. In the row check, there would be a moment when j == 3. This shouldn't happen. 

    Solution: remove the if(j < 3) and if(i < 3). Replace then with this.

    if(j >= 3 || i >=3){return 0}

This is the complete code. Try it. 

source code

Next Post -> Self-playing pacman. Using recursive, we can make a pacman moves and search its food in the  entire area. 

Component - Proxificator

In this semester, I took Component Oriented Programming. What is that? It is a way of programming that make a certain function can be reused by other developers.

As the assignment, my friends and I made one component. We call it Proxificator, because it does some actions related with proxy. There are 3 basic functions.

1. Get Proxies. We provide functions to extract proxy list from a certain website and keep it without duplication. 
2. Judge Proxy. We provide functions to judge the quality of a proxy. It can be determined as Elite (recognized as another computer), Anonymous (known that you are using a proxy but your real IP is save), or Transparent (known that your are using proxy and your real IP is known). Besides, we also provide a way to know how fast the proxy works.
3. Use Proxy. We provide functions to use the proxy on the Operating System settings. 

You can get the full source code, the component, and the sample application using Proxificator (if you are non programmer that needs some useful application).

download Proxificator

Recursive 3 - Get Gold part 1

previous post

We're going to play "Get Gold" game. This is a game of finding gold which is represented by value 1 in 1 or 2 array dimension. In this chapter we'll focus on the simplest game play, where there are only three blocks in array. The character should find gold in this area.

There you can see, the dog-like picture is our avatar. He should find the gold, which is represented by yellow rock. We can only move forward and backward.

Why using recursive?
In this example, it's not really the best solution if we use recursive. We can just iterate the array from 0 to 2 and check whether there is gold or not. But, if we want to make it as animation, where the dog moves to next block one by one from the starting point to the gold position and from the gold position to the starting position. (or it will go to the right most block if there is no gold). In this case we'll find that using recursive is a bit helpful. We don't need to write line to make the dog walk to the starting position. Be thankful, we've got the RETURN statement. I know, it's not a big thing. We'll see another advantages in the next chapters.

What is happening if the dog tries to find the gold?

1. If the dog has gold and is in the starting position, (to step 6)
2. If the dog hasn't got the gold, he checks, whether on his block position the gold exists, (to step 3). Else (to step 4)
3. If the dog find the gold, he will bring the gold (to step 4) Else (to step 5)
4. He will move to the left (to step 1)
5. The dog will move one step to the right. (to step 1)
6. Finish

That is what happening. If you don't get it, see this picture. 

Now we'll make the code. 

1. The blocks can be made from an array. The gold can be represented by 1 and empty block with 0.
2. The recursive function is very simple. We need one parameter to keep the position of the dog. Let's call it j.
3. Inside the recursive function we'll check whether the position is still in the size of array or not. Since the size is 3, we'll make it j < 3
4. Then we will check if there is gold or not. Just check the value, if it is 1 then there is gold, if it is 0 then there isn't
5. If the dog find gold, just do return.
6. The initial calling of the method is done in the main function. Just start at position j = 0, by calling find_1(0)

Source Code 1

If you've tried it, you'll only get output "Got Gold"
So, where is the process?

Try this one. You can see the process by printing the array value and giving delay in your program.

Source Code 2


I added two functions. The first one, delay, is used to delay the process in the program so that our eyes can catch up the speed. The other one is the view function, which shows the position.

There you've finished making an animation using recursive. This is the simplest one. If you have any questions or advice please comment.

See you at the next part.

Recursive 2

previous post

We've been talking a bit about recursive, and we're still wondering how to stop the recursive. Now we're talking about it. I have another case for an example. 

Remember this operator ! in math. Yes, it is factorial. If I have 3!, what's the result? 6 of course. That's too easy. But, I want to ask you, how did you find 6 from 3!? 

3! = 3 * 2 * 1

    = 6

Okay. That's correct. Now, what about 2!

2! = 2 * 1

    = 2

Can I replace some parts in 3! equation with 2! ? See the red-colored text. 

3! = 3 * 2 * 1

    = 3 * 2!

You should have got a clue about the recursive. You don't? It's actually a recursive. If you want to know the result of 3! you need to find 2! . In general we can say that to find x! you need to find (x-1)! 

X! = (X-1)!

If you've got the recursive idea, let's write it as code. This is the factorial function. 

int factorial(int n)
{
    return n * factorial( n-1 ); 
}

int main()
{
   int result = factorial(3);
   printf("%d\n",result);
   return 0;
}


You can see the recursive is working in that code. Now, we're getting to the main topic in this chapter, which is how to stop the recursive method. In our case, the factorial will end when it meets 1. What we need to do, is add a conditional statement. We need to make a different action when it meets 1 as n. See the example below.



int factorial(int n)
{
    if(n == 1)
        return n;
    else 
        return n * factorial( n-1 ); 
}

int main()
{
   int result = factorial(3);
   printf("%d\n",result);
   return 0;
}


If you understand this things, let's move on to a more interesting example. We'll use recursive to make some 2D AI. On the next chapter of course. :)

next post