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?