Link to problem: www.spoj.com/problems/MATSUM/
I tried this using 2D segment Tree. This was the first time i implemented 2-D segTree, hence i am not sure whether this is the correct/efficient implementation for it.
Here is my code: ideone.com/ysu8Tr
Can this question be solved by 2-D segTree? If yes, Kindly suggest some ways to improve the efficiency of the code.
Thanks in advance
2D segment tree won’t work unfortunately. You have to use 2D BIT to solve this problem.
is there a difference in the complexity of these two methods? kindly elaborate…
no difference in complexity but segment tree’s constant is much more larger and I haven’t seen a solution using 2d segtree for this problem.
thanks a lot! AC using 2-D BIT… BIT is indeed much faster than segTree