DataStructures.jl icon indicating copy to clipboard operation
DataStructures.jl copied to clipboard

Add segment tree

Open AliceRoselia opened this issue 2 years ago • 4 comments

I am adding the segment tree data structure to the Datastructures.jl.

Thanks for reviewing and I am hopeful this code will be accepted.

AliceRoselia avatar Jul 20 '22 03:07 AliceRoselia

What happened? I didn't mess with these files.

I don't know anymore what is happening.

AliceRoselia avatar Jul 20 '22 04:07 AliceRoselia

Okay... whatever. The old stuffs are failing? Whatever. I think this is fixed/something in the future updates but I don't know.

AliceRoselia avatar Jul 22 '22 03:07 AliceRoselia

I think the reason for these errors is that you have defined a function sizeof in your code without first importing Base.sizeof. This means that your sizeof function hides all the sizeof methods in Base. Since Base.sizeof is a widely used function, hiding it will break many things.

Please note that the principal maintainer of DataStructures, user @oxinabox, has prioritized the process of getting all the current data structures ready for a major release, and inclusion of new data structures has a lower priority.

StephenVavasis avatar Jul 28 '22 14:07 StephenVavasis

I have argued before that such Data Structures are really only useful in an competitive programming environment. For instance, one can do these exact operations on an AVL/Red Black Tree.

I think there is greater utility in this data structure being a standalone package, rather than being included in DataStructures per se.

Lastly the usage of the term Segment Tree is actually ambiguous. The term is used here in a competitive programming setting is different then https://en.wikipedia.org/wiki/Segment_tree as it makes the assumption that all segments are length 1.

SyxP avatar Sep 01 '23 07:09 SyxP