I was solving the problem http://www.spoj.com/problems/LIS2/ on spoj. I tried for days but
could not come up with a solution that could pass(time wise). Then I googled and found
people talking about 2D segment tree.I searched a lot but could not find a descent explanation.Is there any other solution to this problem ??
Also on topcoder i found people say this problem is similar to www.spoj.com/problems/NICEDAY.I had solved this problem way long back and that time I even did not know 1D segment tree.
So can anyone suggest some solution to LIS2 preferably with 2D segment tree.
PS: I am not looking for codes please don't post codes a broad explanation of implementation and space/time complexity of data structure will suffice.
Refer to this link : http://e-maxx.ru/algo/segment_tree
Although the page is in Russian, but Google Translate would be good enough. This page explains the 1-D segment tree first. On the bottom, there is a section titled 'The two-dimensional tree segments in its simplest form' which would give you the required explanation.