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.
Take a 2D BIT, and once the 2D array is converted to a 1D array and is sorted, for each element in the array, starting from the largest, add 1 to BIT [x][y], where x,y are the indices of the element in the original 2D array, after that you find the sum of the values in the BIT within the rectangle (0,0),(x,y), and add it to the answer. I’ll tell you why this works, the conditions specified in the problem were : 1) x1 <= x2 2) y1<=y2 3) a[x2][y2] < a[x1][y1] By adding the elements starting from the largest, you can say for sure, that any element whose coordinates have been recorded in the 2D BIT, is definitely larger than the current element that you have taken, that takes care of condition 3, and by taking the sum of the rectangle, you’re making sure that the conditions 1 and 2 hold true.
1 Like
Thank you bro. After a lot of pen and paper trial and your help, I am finally able to understand. For 1D I always used online algorithm. Never knew it can be done offline like this (eliminates co-ordinate compression). Out of curiosity, can it be solved using online processing? I tried it (after compression), but couldn’t solve.
Anyway, thanks a lot 