Boost logo

Boost :

Subject: Re: [boost] Segment Tree Implementation for GSoC 2014
From: Kevin Zuniga Garate (kevin.zun_at_[hidden])
Date: 2014-03-08 19:42:14

On 7 March 2014 06:28, Phil Endecott <spam_from_boost_dev_at_[hidden]> 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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at