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: https://www.spoj.com/problems/INVCNT/

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.

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.

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

Oh yes. That’s always possible.

Oh yes, thanks!