I was solving last year's IOI problem Game. In short, you are given an initially empty grid and the problem consists of answering queries "Update element in cell x,y" and "Get GCD of all elements in rectangle x1,y1~x2,y2". Note that the grid is huge (10^9 x 10^9)
If it is solved using 2D segment tree it is pretty straightforward, however reading Bruce Merry's post about it, he suggest that there is more efficient (though harder to code) implementation using balanced binary trees. Obviously 2D segment tree would take O(logR*logC) time and memory per query (R,C are the sizes of the grid), however according to his post you can do it in O(logNu*logNu) time per query (Nu is the number of update operations) and significantly less memory.
I can code and understand how to do it in 1D using balanced binary tree, but I can't seem to find a correct way to extend it into higher dimensions. Can anyone explain how would the given problem be solved using balanced binary trees (not segment trees) ?
Thank you in advance,