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-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[1]. 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:
http://wcipeg.com/wiki/Segment_tree.

-- 
Kevin