Re: [boost] Segment Tree Implementation for GSoC 2014

Subject: Re: [boost] Segment Tree Implementation for GSoC 2014
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2014-03-05 12:51:58

Kevin Zuniga Garate wrote:
> A segment tree is a data structure for storing data and querying and
> updating it in intervals, I haven't found a segment tree library in C++, so
> I thought it may be a good data structure for Boost.

> the segment tree I'm talking about is described here:
> http://wcipeg.com/wiki/Segment_tree

This is an augmented tree where the nodes store the min of the sub-nodes,
right?

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.

Regards,  Phil.