Data structure for dynamic predecessor?

I am asking this because I’ve encountered this problem a lot in the last few days. Im in the need of some stl data structure or so which can maintain a dynamically sorted array (with deletes and inserts) and answer queries of predecessor/successor.

For instance in the problem QTREE3 on SPOJ, im trying to use HLD but i need to maintain such a structure on all heavy paths. I could write out an avl tree or something but my code is already quite long due to HLD. Is there an easy fix?

In QTREE3 we are asked only for paths from node 1 to node v; I was thinking it asked for any two nodes u,v.
However, my (mistaken) version of the problem seems interesting. How would you solve it with HLD?:smirk:

Won`t multiset do the thing for you ?

1 Like

Does multiset have k-th order statistics though? AFAIK in multiset you can’t get like the largest number smaller than k in the given set, or say, the k-th smallest element etc.
Or am I wrong?:thinking:

Have a look at this