On 7 March 2014 06:28, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:
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.
Now I have a more clear idea on how I can implement a segment tree using augmented trees and the resultant data structure would be even better in some aspects.
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?
I have just started reading Boost.Intrusive documentation, and also I'm taking a look at Jeff's code. After reading about augmented trees I think it would be great if I can work on completing and improving this extension for Boost.Intrusive. That would be a better addition for Boost, right? Do you think it is also a good proposal for GSoC, or would it be too complex?
(Do you have a motivating application?)
Principal reason for this is learning, I'm not involved with any real application of segment trees right now. -- Kevin