Using segment tree merging to solve problems about sorted list

Revision en1, by TLE, 2016-12-31 15:47:14

Two months ago, I came across a problem. Initially there are n elements, they are in n tiles. There are 3 kinds of queries: 1. merge two tiles into one tile. 2. split one tile into two tiles. (Formally for a tile of size k, split it into two tiles of size k1 and k2, k=k1+k2, the first tile contains the smallest k1 elements and the second tile contains the rest) 3. find the k-th smallest element in one tile. I posted this problem in stackoverflow but no one answered :/ Recently I found this technique (in Chinese) which can be used to solve this problem.

Tags segment trees, algorithmic techniques


  Rev. Lang. By When Δ Comment
en2 English TLE 2016-12-31 16:05:58 3310 Real initial revision :( (published)
en1 English TLE 2016-12-31 15:47:14 680 Initial revision (saved to drafts)