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

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. 

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

Recursive

I've heard a lot of people saying that recursive is difficult to understand. I think, it's true. But, if every lesson is too easy, why would people build school, college, and university.

Let's take a look at recursive. 

 

It's like calling our own name.

We can call our friends, our teachers, our family, but don't forget that it's also possible to call our self. Try to imagine this situation. If you get it, let's continue. 

In programming, we can make a main function. Inside this, we can call another function or method. But we can also call a method within the method itself. Can you see the similarity? I'll give an example in C language. 

The left picture shows that the main()  can call the Calling() method. You could imagine that main() is a person, and Calling() is main()'s friend. 

The right picture shows that, even inside the main(), we could call the main() itself. This is when main() got lonely and call itself. This kind of situation is called recursive. 

It isn't that difficult right. Let's talk about the output. 

The left source code, produces a single line output saying "Hello someone" while the right one produces the same line but written infinitive. It won't stop. Why is this happening? 

The left one works this way.

1. main() calls Calling()
2. Calling() does it's task which is write "Hello someone"
3. After Calling() finished it's task, main()'s first task is done. It continues to system("pause")
4. End of program

The right one works this way.

1. main() calls Calling()
2. Calling() does it's task which is write "Hello someone"
3. After Calling() finished it's task, main()'s first task is done. It continues to main().
4. when main() is called, it does step number 1 until 3 again. 

The process in the right source code will never end. Why? Because main() doesn't know when to stop. Then how could we make it stop? Figure it out yourself or read the next chapter. :)
next post