期刊
SIAM JOURNAL ON COMPUTING
卷 40, 期 2, 页码 465-492出版社
SIAM PUBLICATIONS
DOI: 10.1137/090779759
关键词
range queries; lowest common ancestors; arrays; trees
资金
- German Research Foundation (DFG)
Given a static array of n totally ordered objects, the range minimum query problem is to build a data structure that allows us to answer efficiently subsequent on-line queries of the form what is the position of a minimum element in the subarray ranging from i to j?. We focus on two settings, where (1) the input array is available at query time, and (2) the input array is available only at construction time. In setting (1), we show new data structures (a) of size 2n/c(n) - Theta(n lg lg n/c(n) lg n) bits and query time O(c(n)) for any positive integer function c(n) is an element of O(n(epsilon)) for an arbitrary constant 0 < epsilon < 1, or (b) with O(nH(k)) + o(n) bits and O(1) query time, where H-k denotes the empirical entropy of kth order of the input array. In setting (2), we give a data structure of size 2n + o(n) bits and query time O(1). All data structures can be constructed in linear time and almost in-place.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据