On 03/06/14 18:04, Kevin Zuniga Garate wrote:

On 4 March 2014 09:30, Larry Evans wrote:

...

There was a thread in August 2011 in this list with subject:

[fusion] segmented fusion 2.0

It was started by Eric Niebler. I'd guess he'd be interested.

-regards, Larry

After reading that thread and the linked paper, I understand that they use the word segmented to mean non-contiguous memory, is that correct? OOPS. My mistake. I just assumed the same name implied the same or similar concept.

Sorry for noise :(

Normally a segment tree is build as a heap, in a linear array, and the segment part refers to the intervals.

On 5 March 2014 12:51, Phil Endecott 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

On 7 March 2014 06:28, Phil Endecott wrote:

Well, an "augmented tree" is just any kind of tree where there is any kind of "augmentation"; I think that's orthogonal to whether the internal nodes store data. But that's just a matter of taxonomy.

Now I have a more clear idea on how I can implement a segment tree using augmented trees and the resultant data structure would be even better in some aspects.

I don't think ICL is relevant, except that ICL could be re-implemented using augmented trees (interval trees). Of more interest is Boost.Intrusive, which would could be extended to support augmented trees as Jeff Snyder has proposed in one of the threads that I linked to before. Are you familiar with Boost.Intrusive?

I have just started reading Boost.Intrusive documentation, and also I'm taking a look at Jeff's code. After reading about augmented trees I think it would be great if I can work on completing and improving this extension for Boost.Intrusive. That would be a better addition for Boost, right? Do you think it is also a good proposal for GSoC, or would it be too complex?

(Do you have a motivating application?)

Principal reason for this is learning, I'm not involved with any real application of segment trees right now. -- Kevin