On 5 March 2014 12:51, Phil Endecott
This is an augmented tree where the nodes store the min of the sub-nodes, right?
Yeah, kinda, all the real elements of the tree are in the leafs, and the internal nodes store the min of their sub-trees, but these internal nodes aren't real data of the tree. From what I have read about augmented trees the internal nodes have real elements apart from the additional data, through this may be just a minor thing. Also in a segment tree insertion in a specific position is not covered, just update certain element, or update a whole interval, the same goes for queries, it's used to solve problems like this: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4150 http://www.spoj.com/problems/SEGSQRSS/ http://www.spoj.com/problems/LGLOVE/
There have been various discussions of augmented trees on this list in the past, e.g.
http://thread.gmane.org/gmane.comp.lib.boost.devel/236328 http://thread.gmane.org/gmane.comp.lib.boost.devel/237984
If we had a generic augmented tree facility, e.g. as a Boost.Intrusive extension as Jeff Snyder has proposed, then I think that these segment tress could be implemented using it.
These augment trees are really interesting, I'll look more into them, thanks. Also, a general question that I'm wondering about, would it be better to construct a segment tree that compiles on its own, or should it use other Boost libraries? (I am asking from what I've read in that second thread about ICL). -- Kevin