Segment tree: quick and easy

On the eve of the next course launch “Algorithms for developers” we spent public lesson. They talked about the well-known idea of a tree of segments, discussed how to build it, update it, and quickly. O(log n) calculate the sum of the numbers of any segment of a given array. The algorithm is very simple and economical: you need O(n) memory. To consolidate the material, they solved the olympiad problem.

The webinar was conducted by an experienced programmer and teacher, as well as the head of the course “Algorithms for Developers” Evgeny Volosatov.

The saying

A tree of segments is a data structure that allows algorithmically simple and logarithmic quick finding of the sum of the elements of an array on a given segment.

For example, imagine that you need to find the sum of the following numbers:

Moreover, we need not just to calculate the sum of the numbers of the specified sequence (the sum of the elements of a certain array), but find the sum of any sequence of these numbers as quickly as possible. That is, we can ask some interval (segment) and give the answer as quickly as possible, what is the sum of the numbers from this interval:

What does it mean fast? It means faster than if we just summed the numbers. After all, there can be millions and billions of numbers …

It was the desire to quickly find the sum of consecutive elements that became the motivation for our webinar. Moreover, we are talking not only about the sum, but also about other tasks, for example, calculating any associative function. Thus, we are talking about operations whose execution does not depend on the calculation order.

Let’s return to our row:

Obviously, if we want to find the result quickly, we need to calculate some amounts in advance. The first thing that comes to mind is folding in pairs:

Now, if you need to find the sum of numbers, we can do it almost instantly. For example, to find the sum of the segment mentioned above, it will be enough to add 13 to 9. Everything is elementary: to find sums of four numbers we folded only two.

We complicate the task:

To find the sum of this segment, we need to add up the elements that, one way or another, cover our segment:

Of course, 3 + 13 + 19 = 35. Pay attention to find the sum of seven numberswe folded only three. If the segment consisted of a thousand elements, it would be enough to add an average of 10 elements, since we have a logarithmic complexity with a base-2 logarithm. And it’s fast!

Full binary tree

A complete binary tree is a tree, each element of which has exactly two children.

To work with a complete binary tree, you can and should use a data structure such as an array. Numbering this array is convenient from one.. We number each element of the binary tree with natural numbers from 1 to 2ⁿ-1:

The whole beauty of the approach is that it is very easy to calculate the number of children and parents.
The formula for calculating the “left child”: i * 2, “Right”: i * 2 + 1.

For example, we calculate the numbers of children in the fifth element:

5 x 2 = 10;
5 x 2 + 1 = eleven.

And how from the “child” to rise to the “parent”? Use integer division i / 2

.
Ok, and how to determine whether the child is left or right?
The answer is as follows: left children have even numbers, right children have odd numbers.

Remember these points.

Returning to our example of a binary tree, we ask ourselves, how can we build it? Look, we first have an array of numbers:

For it you need to build a binary tree. How much memory is needed to store the binary tree, at the bottom of which are these elements?

The answer to this question is 2n, if n is a power of two.

We go further, because two more questions arise before us:

from which element do you need to place the source numbers in an array of a complete binary tree?
from which element and in which direction will we start filling our tree with pre-calculated amounts?

The answer to the first question is quite simple: we have 8 elements, in total there will be 16 elements in the array, which means that the first element will be numbered 16 – 8 = 8. And we will start building from left to right and from bottom to top, starting from element 7, adding up values in children, like this:

Next, you need to determine how to find the sum of the desired segment. Let us return to our first example, number the elements and define a segment, and we denote the first element in the segment to be added by the letter L, and the last by R:

Now it is necessary to introduce one more concept so that the algorithm of actions is clear. We are talking about the concept of fundamental elements and their corresponding fundamental segments. The fundamental element is any element from the entire array, and the fundamental segment corresponds to it, that is, those elements from the initial array that are its immediate children / grandchildren. For the fundamental element with the number 4 “5”, the fundamental segment will be from 8 to 9 elements: [“2”; “3”]:

As for the fundamental element with the number 10 – “7” (we designated it L), it coincides with its fundamental segment. Is it possible to expand this fundamental segment without going beyond L-R? In our case, you can. The rule for the left border is this: if it is a left child, then the fundamental segment can be expanded, the new fundamental element will be the parent of the current one. That is, we can write the following in the program:

Now let’s move on to the right element R. It is a fundamental element and a left child, so we can no longer expand the area (we will go beyond the segment). So, we can add this element to the answer:

Next, you need the left element to move to the right, and the right to the left. For the left element with index L = 10, the next index is 5, because it will go to the parent. But it will go first to the right, and then up:

So, the value of L moved to a higher level and a little to the right. How will R decrease? Using the formula (R – 1) / 2.

Here is such an algorithm. As for the following values of the variables L and R, then they will be moved as follows:

If there are not 8 elements in the tree, but an inconvenient number, say 12, we will have to add the tree (the binary tree must be complete) to 16.
The formula for calculating the number of elements (the whole part of the logarithm is taken):

Now we calculate the associative function of finding minimum. Here is our tree and cut:

How many times do you think element 5 will be involved in our function – one or two? Of course, one, but how is this checked in the algorithm? In fact, this element is either a left or a right son, which means that the action will be performed for either L or R.

Now consider the change operation. Let’s say some element has changed, for example, instead of 7, 0 came in. In order for our segment tree to remain in working condition, we need to update all parents, and we need to go to the very top.

Solution of the olympiad problem

One of the requirements for such tasks is that everything should work quickly. So, we have the following condition:

We will solve it using knowledge about the tree of segments. As a result, we get the following C # code:

We send for verification, we see that the decision is made and is complete, which means our algorithm works.

That’s all, if you want details, watch the whole video. You can also read the following author’s articles by our teacher at your leisure Evgenia Volosatova on Habré:

– Balancing red-black trees – Three cases;
– The horse moves on bits. Chess Bitboard.