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,
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:
> There have been various discussions of augmented trees on this list in
> the past, e.g.
> 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).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk