How to count number of inversion in an array using segment tree?

1

I had solved this question using merge sort tree and now I want to solve this using ST.
Can you you help me in doing this and if possible also provide the full code .
Problem Link: SPOJ.com - Problem INVCNT

2

Process the array from left to right. Now when you are at the index i, you want to count all the elements smaller that A[i], which is to the left of i. For this make a query(0, A[i] - 1) in the segment tree. This is true because the segment tree is going to store the frequency of the occurrence. So after the query, do an update(A[i], 1), which adds a +1 to the index A[i] in the segment tree.

2 Likes
3

Is it possible to count inversions using seg tree when N \le10^5, and a[i] \le 10^9?

I know how to do it using merge sort, but just asking is it possible using seg tree?

4

Nope. It’s only possible for A_i \le 10^6. Because we need a frequency array. And also not possible with negative number. Also, I’d suggest using a fenwick tree instead of a segment tree. It takes lesser space and is faster.

You can maybe do some sort of compression as mentioned below.

P.S: In \LaTeX \le produces \le.

1 Like
5

Yes it is. Just map it to a permutation.

Very short code to map into a permutation. 
vector<int> seq(n);
    for(auto &x : seq){
        cin>>x;
    }
    vector<int> mapper(seq.begin(), seq.end());
    sort(mapper.begin(), mapper.end());
    mapper.resize(unique(mapper.begin(), mapper.end()) - mapper.begin());
    for(auto &x : seq){
        x = lower_bound(mapper.begin(), mapper.end(), x) - mapper.begin() + 1;
    }
3 Likes
6

Oh yes. That’s always possible.

1 Like
7

Oh yes, thanks!

8

Any relation between the minimum number of swaps required to sort an array with inversions of the array?
How we can count min swap with seg tree?
[2,4,5,1,3] => inversion -5
min swap -3 (as per dfs cycle solution)