Re: [boost] Segment Tree Implementation for GSoC 2014

Kevin Zuniga Garate wrote:

On 5 March 2014 12:51, Phil Endecott wrote:

...

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.

Well, an "augmented tree" is just any kind of tree where there is any kind of "augmentation"; I think that's orthogonal to whether the internal nodes store data. But that's just a matter of taxonomy.

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).

I don't think ICL is relevant, except that ICL could be re-implemented using augmented trees (interval trees). Of more interest is Boost.Intrusive, which would could be extended to support augmented trees as Jeff Snyder has proposed in one of the threads that I linked to before. Are you familiar with Boost.Intrusive? (Do you have a motivating application?) Regards, Phil.