Spoj MATSUM TLE

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 :slight_smile:

2D segment tree won’t work unfortunately. You have to use 2D BIT to solve this problem.

1 Like

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.

ok… thanks :slight_smile:

thanks a lot! AC using 2-D BIT… BIT is indeed much faster than segTree :slight_smile:

1 Like