segment_tree: Segment Tree
Description Usage Arguments Details Value References
Description
Fast segment tree class exposed as an Rcpp Module.
Usage
1 | segment_tree(intervals)
|
Arguments
intervals |
an (n x 2) matrix of intervals. |
Details
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.
Value
A queryable segment tree.
References
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.
