 # Segment Tree problems of Codeforces edu with code and some explanation

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

This is the easy problem, just using Inclusion and Exclusion principle and Segment Tree for the Sum.
Here is my AC solution

9 Likes

Nice work bro 1 Like

Thanks brother. I will do them as practice problem.
Comment for marking this post for viewing later.

i m getting WA on test case 6 for addition to segment

the above is my soln
I use 1-based indexing
can u figure out where i am making a mistake
@kapil16garg

Update: Done

At line 50
I think it should be
st[si].pref += a[ss];

1 Like

There is another resource about a complete introduction to Segment Tree and also with Lazy technique and persistent technique.

You can find it at the following link

1 Like