CODEWITHSUNDEEP
data-structuressegment-tree
sasha sami
sasha sami

Reputation: 525

How to code 2D segment tree?

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.

Upvotes: 1

Views: 3248

Answers (1)

divanshu
divanshu

Reputation: 345

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.

Upvotes: 1

Related Questions