Here are the CODEFORCES EDU's tasks for Segment Tree, When I solved it I found that how these problems depend on each other. Here I tried to explain the problem's approaches with code in a very simple way.
Segment Tree Problems -
1- Segment Tree for the Sum — This is the basic and easiest question of the segment tree. Here is my AC simple solution
2- Segment Tree for the Minimum — Here we have to find the minimum element from a segment and can also update an index.This is also a basic problem of Segment Tree. Here is my AC simple solution
3- Number of Minimums on a Segment — This question is an upgrade version of Segment Tree for the Minimum when we calculate the number of minimums on a Segment, then you should not go on every leaf node to find minimums if you will do it then it will give TLE on 55 or 75 test cases, so the optimized approach is that here will use of pair<int, int> and store the min element and count ({min, count}) at the time of tree building for each node.
4- Segment with the Maximum Sum — In this question, we have to merge two nodes in an optimal manner so every node has a maximum sum of its segment, so for this, we have to maintain max suffix, max prefix, max segment, the sum for every node. Here is my AC solution
5- K-th one — Just find an index of kth one and also can update the index This question is the application of Segment Tree for the Sum, only one thing keep in mind is that In the query part if
` if(tree[index]<k)`
{ k -= tree[index]; return INT_MAX; } Here is my AC solution
6- First element at least X — Here we have to find the minimum index j such that a[j]≥x. This question is simple application of segment Tree for the maximum ,go every node and check this condition if tree[index]<x then return otherwise continue operation.
Here is my AC simple solution
7- First element at least X — 2 — This is the upgrade version of First element at least X, just add a simple condition (if(se<l) return;) in the previous solution. Here is my AC solution
8- Inversions — Here you do not need to build tree function because in initial all tree nodes will have value 0, and in the query part just check the sum between( a[i]+1 to n ) using Segment Tree for the Sum and update every a[i] with 1. Here is my AC solution
9- Inversions 2 — This is the reverse version of Inversions, just think in reverse Here is my AC solution
10- Nested Segments — This is an application of Segment Tree for the Sum, we iterate left to right, and at the time of the first occurrence(left) of a[i], we will store the position pos of a[i], and at the time of the second occurrence(right) of a[i], (curr = i) we will calculate sum betweenpos to curr by using range sum query and update left position (pos) by 1. Here is my AC solution
11- Intersecting Segments — The only difference between Nested Segments and this problem is that we have to iterate given array two times first left to right and right to left, at the time of the first occurrence (left) of a[i] (pos = i) we will update pos of a[i] with 1 and at the time of the second occurrence (right) of a[i] (curr = i) we will calculate sum betweenpos to curr by using range sum query and update left position (pos) by 0. Here is my AC solution
12- Addition to Segment — This is the easy problem, just using Inclusion and Exclusion principle and Segment Tree for the Sum. Here is my AC solution
Thanks to pashka for the amazing tutorials.
If you like please upvote it.
For Intersecting Segments problem I wanna suggest another solution, we can calculate no. of intersecting segments for number i using the below formula:
intersecting segments = no. of total elements between both occurences of number i — 2 * no. of nested segments.
For eg. 3 2 2 1 3 -> intersecting segments for 3 = 3 — 2 * 1 = 1.
Accepted code
For Intersecting Segments problem I wanna suggest another solution in a single iteration, :] from left to right: update the position of the first occurrence of
arr[i]to 1 , on finding the second occurrence ofarr[i]at positionjthe answer is to query the sum of range i+1 to j then updating j to 1, and i to -1, So whenever you query a range , the nested segments fade each other.