Segment Tree Implementation for GSoC 2014
Hello everyone, I'm Kevin and I'd like to contribute to Boost in this SoC. I enjoy coding in C++ and participate a lot in competitive programming sites such as TopCoder, Codeforces, etc. 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. Do you think that would be a good addition for Boost? If not, what other data structure would you like to see implemented? Greetings. -- Kevin
On March 3, 2014 11:08:22 PM EST, Kevin Zuniga Garate <kevin.zun@gmail.com> 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. ___ Rob (Sent from my portable computation engine) [1] http://www.boost.org/doc/libs/release/libs/icl/
On 4 March 2014 05:16, Rob Stewart <robertstewart@comcast.net> wrote:
On March 3, 2014 11:08:22 PM EST, Kevin Zuniga Garate <kevin.zun@gmail.com> 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
On 03/03/14 22:08, Kevin Zuniga Garate wrote:
Hello everyone,
I'm Kevin and I'd like to contribute to Boost in this SoC.
I enjoy coding in C++ and participate a lot in competitive programming sites such as TopCoder, Codeforces, etc.
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.
Do you think that would be a good addition for Boost? If not, what other data structure would you like to see implemented?
Greetings.
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
On 4 March 2014 09:30, Larry Evans <cppljevans@suddenlink.net> 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? Normally a segment tree is build as a heap, in a linear array, and the segment part refers to the intervals. -- Kevin
On 03/06/14 18:04, Kevin Zuniga Garate wrote:
On 4 March 2014 09:30, Larry Evans <cppljevans@suddenlink.net> 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.
Kevin Zuniga Garate wrote:
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.
the segment tree I'm talking about is described here: http://wcipeg.com/wiki/Segment_tree
This is an augmented tree where the nodes store the min of the sub-nodes, right? 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. Regards, Phil.
On 5 March 2014 12:51, Phil Endecott <spam_from_boost_dev@chezphil.org> 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
Kevin Zuniga Garate wrote:
On 5 March 2014 12:51, Phil Endecott <spam_from_boost_dev@chezphil.org> 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.
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.
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).
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? (Do you have a motivating application?) Regards, Phil.
On 7 March 2014 06:28, Phil Endecott <spam_from_boost_dev@chezphil.org> 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
participants (4)
-
Kevin Zuniga Garate -
Larry Evans -
Phil Endecott -
Rob Stewart