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;`
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 between pos 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 between pos 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
