Subject: Re: [boost] Segment Tree Implementation for GSoC 2014
From: Kevin Zuniga Garate (kevin.zun_at_[hidden])
Date: 2014-03-04 08:07:44
On 4 March 2014 05:16, Rob Stewart <robertstewart_at_[hidden]> wrote:
> On March 3, 2014 11:08:22 PM EST, Kevin Zuniga Garate <kevin.zun_at_[hidden]> wrote:
> >A data structure I have learn from participating in those contests is
> >segment tree.
> >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.
> I know nothing about that data structure but what Wikipedia tells me. There I noted two things. First, the data structure is similar to an internal tree, which makes me wonder how it compares to Boost.ICL. Second, they say it's immutable, but you mentioned updating it.
I looked at the Wikipedia article, it seems that there are two data
structures with the same name, if you look at the article's discussion
page there is actually a talk about renaming the article.
The segment tree described in Wikipedia is indeed similar to an
interval tree, the segment tree I'm talking about is described here:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk