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?

BIG EDIT:
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

2 Likes