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.