Now, we will discuss how to calculate a sum on a segment.

You start on segments in this segment tree but not every segment.

So if you have some different segment as a query,

you need to partition the segment to segments which are stored in segment tree.

As you know, they all have a length of power of two and starts in

a cell which is some multiple of this power of two..

There are two way,

in fact you can go upwards on a tree or downwards.

Going upwards is the fastest way but it's less universal.

Some operations are harder to implement,

but for basic operations,

both ways are okay.

Let's consider some query and you can just easily move the square root

into the tree because of the leaves of the tree start in the successive cells,

and they represent just an original array.

You can just add the lengths of the original array to the positions of the query.

Now the new task is to calculate the sum inside the two.

How to solve this task?

This task is solved, as I said,

we will go upwards and we'll just need

to reformulate the task so you can move just one level up.

Now, we will solve the task inside the tree.

So, the left and right boundaries.

There are some easy cases when the left boundary is larger than right boundary,

there's just an empty sum which is obviously equal to zero.

And if the boundaries are equal,

their sum is just one element of the tree which is obviously the answer.

The general case is the case when there are at least two elements.

And let's look at the left boundary.

There are just two cases which the left boundary can be odd or even.

If it is even,

the next cell it's just another child of the same parent.

So, we can start,

and then level up,

and just divide the number of left cell by two,

and move level up.

But if it's not even,

it can be odd,

just accumulate the value of this cell to some variable S,

and then just increment the left boundary.

So we can always be in the case when the left boundary is represented by an even number.

The same can be done with the right boundary.

If right boundary is even,

we can make it odd just by accumulating its value to the variable S

and then decrementing its value.

So, when the L is even and R is odd,

just divide them by two and we move one level up,

and the segment inside the tree is exactly the same segment,

is exactly the same segment of the original array,

you had end up one level down.

When the process is terminated,

it is terminated when there are one or zero elements,

you will have the answer to the query in the variable S. The complexity of

this algorithm is obviously logarithmic because there is a logarithmic number of levels.

If we consider the size of the array as N,

then K is a binary logarithm of N. You can

prove that the case of one element is unnecessary,

you can just terminate when L becomes greater than R. So,

you can see the code.

The code is very simple.

It's just one while loop inside,

you just modify the variables L and R in the way we described.

So, maybe the picture can easy illustrate this process to you.

Calculating the sum downwards is

more universal way because when you go downwards the tree,

the old functions look very same,

they all look the same.

So, let's consider a query,

and we will solve the task at some node V,

and we will support these boundaries.

So the original task is finding the intersection of

the query with the segments which is described by the node,

and you just take the elements which lie in this intersection and sum those elements,

and this is the answer.

So, the original task is about doing this at node one and the root of the tree.

And then, we will descend this tree and

then number of node will be maybe some other venue.

We need to go one level down,

and what are the easy cases?

The first easy case is when this intersection is empty.

It's just a few of simple conditions you can check and

then returns zero because the sum is obviously zero.

Another case is that the segment represented by

tree cell is contained in other original query segment.

In this case, you just return the values to R in the tree cell.

The general case is

the empty intersection that has a cell is contained in the query is there.

There's some non-empty intersection but it's not the whole cell.

So just divide this cell by two because

the segment trees are in such a way that cell is divided by two.

And then so, the task for each cell which is a child of the cell we had.

So, it is also a logarithmic algorithm because there are

no more than two segments of each three kinds on

each level because there are no more than two empty intersections,

no more than two intersections,

that's completely in this cell of a tree on this level.

And no more than two general cases,

you can easily prove this.

You can look at the code.

The code is also very simple but slightly larger because we

need some variables to modify.

And you can also look at the picture which

illustrates the process of descending the tree.