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?