RMQ Task - 2. Segment Tree
In the first part of our topic, we looked at the solution of the static RMQ problem for (O (nlogn), O (1)). Now we will deal with a data structure called a segment tree, or intervals (in English literature, a segment tree or interval tree). With it, you can solve dynamic RMQ for (O (n), O (logn)).
We introduce the concept of a tree of segments. For convenience, we add the length of the array to the power of two. We add infinities to the added array elements (beyond infinity we should understand, for example, a number, more than which nothing will appear in the data). So, the segment tree is a binary tree, at each vertex of which the value of a given function is written on a certain segment. The function in our case is the minimum.
')
Each sheet will correspond to an array element with a number equal to the ordinal number of the sheet in the tree. And to each vertex that is not a leaf, there will be a segment of the array elements corresponding to the descendants of this vertex.
Behind the seemingly monstrous definition is a quite simple concept - we look at the drawing.
Explain the definition. The marked vertex will correspond to the marked segment, because it is the union of all the descendant sheets of the vertex (from this moment we identify the leaf and the array element that it represents).
Keep the tree will be like a binary heap. Let's get an array of T [2n - 1]. The root will lie in the first element of the array, and the sons of the i-th vertex will lie in the elements with numbers 2i and 2i + 1 - left and right, respectively. Immediately you can notice the obvious property: T [i] = min (T [2i], T [2i + 1]) for the i-th vertex, which is not a leaf. Sheets, by the way, will lie with this numbering in the elements with numbers from n to 2n - 1.
We construct a tree, running along the elements from (n - 1) through the first, counting the minimum values in the sons for each vertex.
Beginning with this article I will give the code for greater clarity.
The build_tree (V) function turns an array V into a segment tree for this array. So, now how to find a minimum on it on a segment? To do this, we introduce the concept of a fundamental segment.
A fundamental segment in an array is such a segment that there exists a vertex in the tree to which it corresponds. We divide our segment into a minimal number of non-intersecting fundamental ones. We show that at each level their number does not exceed 2.
Take the largest fundamental segment in the partition. Let its length be 2t. Note that the fundamental segments of length 2t are no more than two (1). Take the leftmost of the maximum available fundamental. We will move from it to the left. Note, again, that the lengths of the segments will decrease (2). Also with the right of the maximum. Thus, we obtain that the fundamental segments are at most 2t, which does not exceed 2logn. Clauses (1) and (2) in the proof I leave for self-reflection.
How does this help us? Now we can implement the minimum request “from below”. We will rise from below, adding to the answer at each level, if necessary, a fundamental segment.
Let's get two pointers - l and r, with which we will find the next fundamental segments of the partition. Initially, we set l and r pointing to the sheets corresponding to the ends of the query segment. Note that if l points to a vertex that is the right son of its parent, then this vertex belongs to the division into fundamental segments, otherwise it does not belong. Similarly, with the pointer r - if it points to the vertex, which is the left son of its parent, then we add it to the partition. After that, move both pointers to a higher level and repeat the operation. We continue operations until the pointers enter one by one.
Finding another fundamental segment, we compare the minimum on it with the current minimum found and reduce it if necessary. The asymptotic behavior of the algorithm is O (logn), since at each level we perform a constant number of operations, and the entire levels we perform logn.
Now let's learn how to change the value of a tree item. Note that for each leaf there is exactly logn of fundamental segments that contain it — they all correspond to vertices lying on the path from our leaf to the root.
Therefore, when changing an element, it is enough just to run from its sheet to the root and update the value at all vertices on the path by the formula T [i] = min (T [2i], T [2i + 1]).
Hooray! We obtain the solution of the Dynamic RMQ problem for (O (n), O (logn)).
In the next article we will learn how to make a request from above. Despite the fact that the asymptotics of the query from above will be the same, it has one big bun - the ability to easily and naturally tighten the modification on the segment. See you again!
Definition
We introduce the concept of a tree of segments. For convenience, we add the length of the array to the power of two. We add infinities to the added array elements (beyond infinity we should understand, for example, a number, more than which nothing will appear in the data). So, the segment tree is a binary tree, at each vertex of which the value of a given function is written on a certain segment. The function in our case is the minimum.
')
Each sheet will correspond to an array element with a number equal to the ordinal number of the sheet in the tree. And to each vertex that is not a leaf, there will be a segment of the array elements corresponding to the descendants of this vertex.
Behind the seemingly monstrous definition is a quite simple concept - we look at the drawing.
Explain the definition. The marked vertex will correspond to the marked segment, because it is the union of all the descendant sheets of the vertex (from this moment we identify the leaf and the array element that it represents).
Keep the tree will be like a binary heap. Let's get an array of T [2n - 1]. The root will lie in the first element of the array, and the sons of the i-th vertex will lie in the elements with numbers 2i and 2i + 1 - left and right, respectively. Immediately you can notice the obvious property: T [i] = min (T [2i], T [2i + 1]) for the i-th vertex, which is not a leaf. Sheets, by the way, will lie with this numbering in the elements with numbers from n to 2n - 1.
Building
We construct a tree, running along the elements from (n - 1) through the first, counting the minimum values in the sons for each vertex.
Beginning with this article I will give the code for greater clarity.
const int INF = INT_MAX; void build_tree(const vector<int>& V) { // , int n = (1 << (log(n - 1) + 1)); V.resize(2 * n, INF); // for (int i = n; i < 2 * n; i++) V[i] = V[i - n]; // for (int i = n - 1; i > 0; i--) V[i] = min(V[2 * i], V[2 * i + 1]); } The build_tree (V) function turns an array V into a segment tree for this array. So, now how to find a minimum on it on a segment? To do this, we introduce the concept of a fundamental segment.
Minimum request
A fundamental segment in an array is such a segment that there exists a vertex in the tree to which it corresponds. We divide our segment into a minimal number of non-intersecting fundamental ones. We show that at each level their number does not exceed 2.
Take the largest fundamental segment in the partition. Let its length be 2t. Note that the fundamental segments of length 2t are no more than two (1). Take the leftmost of the maximum available fundamental. We will move from it to the left. Note, again, that the lengths of the segments will decrease (2). Also with the right of the maximum. Thus, we obtain that the fundamental segments are at most 2t, which does not exceed 2logn. Clauses (1) and (2) in the proof I leave for self-reflection.
How does this help us? Now we can implement the minimum request “from below”. We will rise from below, adding to the answer at each level, if necessary, a fundamental segment.
Let's get two pointers - l and r, with which we will find the next fundamental segments of the partition. Initially, we set l and r pointing to the sheets corresponding to the ends of the query segment. Note that if l points to a vertex that is the right son of its parent, then this vertex belongs to the division into fundamental segments, otherwise it does not belong. Similarly, with the pointer r - if it points to the vertex, which is the left son of its parent, then we add it to the partition. After that, move both pointers to a higher level and repeat the operation. We continue operations until the pointers enter one by one.
Finding another fundamental segment, we compare the minimum on it with the current minimum found and reduce it if necessary. The asymptotic behavior of the algorithm is O (logn), since at each level we perform a constant number of operations, and the entire levels we perform logn.
int rmq_up(vector<int>& T, int l, int r) { int ans = INF; int n = T.size() / 2; l += n - 1, r += n - 1; while (l <= r) { // l - , // if (l & 1) ans = min(ans, T[l]); // r - , // if (!(r & 1)) ans = min(ans, T[r]); // l = (l + 1) / 2, r = (r - 1) / 2; } return ans; } Modification
Now let's learn how to change the value of a tree item. Note that for each leaf there is exactly logn of fundamental segments that contain it — they all correspond to vertices lying on the path from our leaf to the root.
Therefore, when changing an element, it is enough just to run from its sheet to the root and update the value at all vertices on the path by the formula T [i] = min (T [2i], T [2i + 1]).
void update(vector<int>& T, int i, int x) { int n = T.size() / 2; i += n – 1; T[i] = x; while (i /= 2) T[i] = min(T[2 * i], T[2 * i + 1]); } Hooray! We obtain the solution of the Dynamic RMQ problem for (O (n), O (logn)).
In the next article we will learn how to make a request from above. Despite the fact that the asymptotics of the query from above will be the same, it has one big bun - the ability to easily and naturally tighten the modification on the segment. See you again!
Source: https://habr.com/ru/post/115026/
All Articles