Segment Tree

[mdclyburn]

Segment tree reference for the hackpack. Please review.

Fixes #30.

[mdclyburn]

I have included a separate source file for the reference code to be included in the condensed hackpack. This was easier to do instead of mangling the problem solution source. Problems aren't in the condensed hackpack, are they?

[robertu94]

The problem statements are not, but the solutions should be.

[bcdean]

It's still a bit vague, when reading this, what exactly a segment tree looks like -- can we maybe include a picture or something a bit more concrete in the description that mentions the key feature of how nodes represent "segments" of a sequential data set? I've read the example problem a few times and I still can't understand exactly what it's asking for, even looking at the input and output samples -- maybe this can be clarified a bit. Finally, I think the construction time is O(n) instead of O(n log n). In the code, maybe make it clear how it would need to be modified if we want to do other types of range queries other than range maxes? (e.g., range min, range sum)

[bcdean]

"a segment tree cannot changed" -> "a segment tree cannot change"

[mdclyburn]

@bcdean I have tried to make the problem description and input specification clearer. Failing this attempt, perhaps I can explain it to you in depth so you can help me word it better?

[mdclyburn]

It can be excluded. Removing it is trivial.

[mdclyburn]

@bcdean I've taken some input from @robertu94 into consideration and changed the problem slightly. I have also elaborated on the tree construction a little bit more and also included a couple of graphics showing the layout of the tree in the array as well as an abstract visual in a binary tree format. I will look into a better description on segtree construction tomorrow and notify you again.

[bcdean]

Ok, thanks – I’ll wait until I hear from your tomorrow to make another pass.

From: Marshall Clyburn [mailto:notifications@github.com] Sent: Wednesday, November 11, 2015 9:49 PM To: clemsonacm/hackpack hackpack@noreply.github.com Cc: Brian Dean bcdean@clemson.edu Subject: Re: [hackpack] Segment Tree (#39)

@bcdeanhttps://github.com/bcdean I've taken some input from @robertu94https://github.com/robertu94 into consideration and changed the problem slightly. I have also elaborated on the tree construction a little bit more and also included a couple of graphics showing the layout of the tree in the array as well as an abstract visual in a binary tree format. I will look into a better description on segtree construction tomorrow and notify you again.

— Reply to this email directly or view it on GitHubhttps://github.com/clemsonacm/hackpack/pull/39#issuecomment-155981793.

[mdclyburn]

@bcdean I have included some more information on the construction of the segment tree. Perhaps this will help make it even clearer as to how it works like it does. I have previously included information in the code on how to modify the segment tree to support different operations. I added some more information there to help that out. If that is not okay, then I could alternatively write out multiple implementations.

For the condensed hackpack, the included reference segment tree code is one that stores RMQs only. I could add the information there as well or write multiple implementations, but I'm not sure if that's desirable for that medium.

I would like you to look over the section again and see what you think of it. Especially the problem.

[bcdean]

I like the picture, although I might make the bottom row of the tree fully complete, and indicate somehow that this bottom row is the “actual” data set—the tree on top of it serves to hold augmented information about ranges in the data set of varying sizes (all powers of two), so any query can be decomposed into a combination of O(log n) of these and hence answered in O(log n) time.

Construction takes only O(n) time, not O(n log n) time, using the method you’ve outlined.

Finally, for the sample question, why does it need a segment tree? Can’t you just count the number of cows whose intervals overlap with the target [t1,t2] interval as you go using a simple interval overlap check?

--- Brian

From: Marshall Clyburn [mailto:notifications@github.com] Sent: Thursday, November 12, 2015 10:11 AM To: clemsonacm/hackpack Cc: Brian Dean Subject: Re: [hackpack] Segment Tree (#39)

@bcdeanhttps://github.com/bcdean I have included some more information on the construction of the segment tree. Perhaps this will help make it even clearer as to how it works like it does. I have previously included information in the code on how to modify the segment tree to support different operations. I added some more information there to help that out. If that is not okay, then I could alternatively write out multiple implementations.

For the condensed hackpack, the included reference segment tree code is one that stores RMQs only. I could add the information there as well or write multiple implementations, but I'm not sure if that's desirable for that medium.

I would like you to look over the section again and see what you think of it. Especially the problem.

— Reply to this email directly or view it on GitHubhttps://github.com/clemsonacm/hackpack/pull/39#issuecomment-156133677.

[mdclyburn]

@bcdean OK. I've changed some things again. With regards to the sample problem, what do you think the issue is? Is it that I'm not being clear enough? Is it confusing? I realize that it might be a little more difficult to analyze the problem since I explained it to you. What do you think @robertu94 ? I've excluded the entire 'optional printing' twist and just give different times every time now, so I think that makes things simpler.

[mdclyburn]

Enhancements will be handled by #45 .