Optimal static range reporting in one dimension
Optimal static range reporting in one dimension
复制标题
一维最佳静态范围报告
DOI：
10.1145/380752.380842
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Theis Rauhe
中科院分区：
文献类型：
--
作者：
Stephen Alstrup;G. Brodal;Theis Rauhe
我们考虑静态一维范围搜索问题。 \ {0,1，\ dots，2^<Italic> w </italic> -1 \}，支持<italic> u </italic>的整数间隔的各种查询。斜体> s </italic>包含在查询间隔内，我们提供了一个最佳数据线性空间成本和查询时间线性在整数中报告。近似范围计数的结构。一个近似答案，最多在正确的答案的1+ε之内。
We consider static one dimensional range searching problems. These problems are to build static data structures for an integer set <italic>S</italic> \subseteq <italic>U</italic>, where <italic>U</italic> = \{0,1,\dots,2^<italic>w</italic>-1\}, which support various queries for integer intervals of <italic>U</italic>. For the query of reporting all integers in <italic>S</italic> contained within a query interval, we present an optimal data structure with linear space cost and with query time linear in the number of integers reported. This result holds in the unit cost RAM model with word size <italic>w</italic> and a standard instruction set. We also present a linear space data structure for approximate range counting. A range counting query for an interval returns the number of integers in <italic>S</italic> contained within the interval. For any constant ε>0, our range counting data structure returns in constant time an approximate answer which is within a factor of at most 1+ε of the correct answer.