## PROBLEM-LINK

Author: @praveen3277

Tester: @aneesh2312, @eccentrik, @hellb0y_suru

Editorialist: @praveen3277

## DIFFICULTY

Easy-Medium

## PREREQUISITES

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:

## Tester Solution 1:

@aneesh2312 Solution: https://www.codechef.com/viewsolution/36593011

## Tester Solution 2:

@eccentrik Solution: https://www.codechef.com/viewsolution/36593046

## Tester Solution 3:

@hellb0y_suru Solution: https://www.codechef.com/viewsolution/36593080

**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