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

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 .

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

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?

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

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;
}
``````
2 Likes

Oh yes. That’s always possible.

1 Like

Oh yes, thanks!