Hacker News Reader

You're looking for an implicit interval tree. The key idea is to store sorted ranges and simulate the interval tree via binary search. The best implementation I know of is coitrees: https://github.com/dcjones/coitrees, but you could also roll your own. cgranges is another good implementation: https://github.com/lh3/cgranges

View on HN

Thank you, I should look into these more. I actually came across them earlier but it wasn’t obvious that these would outperform a plain sorted `Vec` with binary search, which seemed to have slightly worse performance than the ordered map I’m currently using. my understanding is that some of the bioinformatics-oriented interval trees assume intervals are mostly static, so they don’t support updates very well without expensive tree rebuilding after each batch of updates.

Yup, a Vec with binary search is basically all these are. Tree rebuilding is "just" sorting the Vec. To the extent that's fast enough for small updates (merge sort with new elements) you can update rather often without issue.

Reply on news.ycombinator.com