data structures - How to code 2D segment tree? -

I was solving the problem http://www.spoj.com/problems/LIS2/ spogues but did not come with a solution, which can be passed (according to time). Then I was singing and people were talking about the 2D section tree . I searched a lot, but no descent details could be found. Is there any other solution to this problem ?? Apart from this, I found people on topcoder to say that this problem is similar to www.spoj.com/problems/NICEDAY . I had solved this problem long ago and at that time I did not even know the 1D section tree .
So anybody can suggest some solution with LIS2 with the 2D section tree .


PS: I am not looking for code Detailed information about implementing the code and complexity of place / time of data structure will not be enough.

View this link:

However the page is in Russian but Google translate It will be quite good. This page first describes the 1-D segment tree. In the lower part, there is a section entitled 'Two-Dimensional Tree Segment' in its simplest form, which will give you the necessary explanation.