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 coordinate 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. asked 07 Aug '16, 20:42
