Fast segment tree class exposed as an Rcpp Module.
segment_tree(intervals)
| intervals | an (n x 2) matrix of intervals. |
|---|
A queryable segment tree.
A segment tree is rooted-augment binary search tree useful for querying information across a fixed set of intervals. This segment tree class is specialized to handle interval queries which return indices of points that intersect the given query interval. The query interval must be composed using endpoints which were used to construct the tree.
Mehta, Dinesh P., and Sartaj Sahni. "Chapter 18: Interval, Segment, Range, and Priority Search Trees." Handbook of data structures and applications. Chapman and Hall/CRC, 2004.