I know how to do it using Fenwick tree on a 1D array. If the size of elements is large, I know how to use co-ordinate compression to bring it into workable range. But I am unable to understand how to do it for 2D array. I know about 2D fenwick tree, just not how to use it in this case.

I am referring this problem.

The solution converts the 2D array into 1D array. After that it uses sorting and then Fenwick tree. This is the part where I am lost. Why use sorting? When we sort, doesn’t the relative order of the elements change?

Can someone explain this part with a simple example?

I am trying to follow *anudeep2011*’s solution.