Re: [boost] Segment Tree Implementation for GSoC 2014

Subject: Re: [boost] Segment Tree Implementation for GSoC 2014
From: Kevin Zuniga Garate (kevin.zun_at_[hidden])
Date: 2014-03-06 20:17:04

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

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