# INVUSTP - Editorial

Author: @praveen3277
Tester: @aneesh2312, @eccentrik, @hellb0y_suru
Editorialist: @praveen3277

Easy-Medium

Segment Tree

## PROBLEM

We are given a permutation of first N natural number in an array A and we are required to find the sum of inversions of each elements in the indices range [ L, R ].

## EXPLANATION

Let us say that we are given this permutation A as { a1, a2, . . . , aN } where each element occurs from 1 to N exactly once, i.e, all elements are distinct. Then to find the sum of inversions in range [ L, R ] first we need to find inversions of each of the elements at each index.

And this we can do using bits in segment tree.

Now let us say that we have found the inversions of the elements at each index as { i1, i2, i3, . . . iN } and using this we can build another segment tree for range sum and then process the query.

The time complexity is O ( nlogn ).

And we are done.

## SOLUTIONS

Setter and Editorialist Solution:

https://www.codechef.com/viewsolution/36592901

Tester Solution 1:
Tester Solution 2:
Tester Solution 3:

PS: I tried to explain it in a simple way.Hope you enjoyed solving this problem in Code Chronicles 2.0. And sorry for my bad English.

Thank You

4 Likes

Correct me if Iām wrong
We need to find the count of all the inversions of elements in L to R
e.g.
5
5 4 3 2 1
query -> 2 3
answer to this query is 1, am I right?

1 Like

No! You have to find the sum of inversions of each element at L, L+1,L+2.....,R.
In the case of 5, 4, 3, 2, 1
query -> 2,3