Ask HN: Fast data structures for disjoint intervals?

Re:Ask HN: Fast data structures for disjoint intervals? by hackermailman on Tuesday July 23, 2024 @10:53AM (#41046598)

Erik Demaine's DS class has a bunch of range trees and cascading method to speed up queries https://courses.csail.mit.edu/6.851/spring21/lectures/

[ Parent | on HN ]

Re:Ask HN: Fast data structures for disjoint intervals? by alex5207 on Tuesday July 23, 2024 @11:30AM (#41047045)

His explanations are great and just wanted to +1 on the idea of range trees. Adding a reference here to a very lightweight read on range trees:

https://courses.csail.mit.edu/6.851/spring10/scribe/lec03.pd...

[ Parent | on HN ]

Re:Ask HN: Fast data structures for disjoint intervals? by grovesNL on Tuesday July 23, 2024 @12:34PM (#41047975)

Thanks, I came across some of Erik's videos in my research but I didn't realize they were part of a bigger series focused on ranges. Cascading methods are exactly the kind of ideas I'm thinking about.

[ Parent | on HN ]