Optimal Succinctness for Range Minimum Queries
Optimal Succinctness for Range Minimum Queries
复制标题
范围最小查询的最佳简洁性
DOI：
10.1007/978-3-642-12200-2_16
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
J. Fischer
中科院分区：
文献类型：
--
作者：
J. Fischer
对于n个全序对象的静态数组A，范围最小值查询要求两个指定数组索引之间的最小值的位置。我们展示了如何预处理A到一个计划的大小为2n+o（n）位，允许回答范围最小查询A在恒定的时间。在预处理步骤之后不允许访问A的重要设置中，该空间是渐近最优的。我们的方案可以在线性时间内计算，只需要n+o（n）个额外的比特来构造。我们还改进了BPS或DFUDS编码树中的LCA计算。
For a static array A of n totally ordered objects, a range minimum query asks for the position of the minimum between two specified array indices. We show how to preprocess A into a scheme of size 2n+o(n) bits that allows to answer range minimum queries on A in constant time. This space is asymptotically optimal in the important setting where access to A is not permitted after the preprocessing step. Our scheme can be computed in linear time, using only n+o(n) additional bits for construction. We also improve on LCA-computation in BPS- or DFUDS-encoded trees.