Opportunistic Data Structures for Range Queries
In this paper, we study the problem of supporting range sum queries on a compressed sequence of values. For a sequence of n k-bit integers, k≤O(log n), our data structures require asymptotically the same amount of storage as the compressed sequence if compressed using the Lempel-Ziv algorithm. The basic structure supports range sum queries in O(log n)time. With an increase by a constant factor in the storage complexity, the query time can be improved to O(log log n/log log log n + k).
Chung Keung Poon Wai Keung Yiu
Department of Computer Science, City University of Hong Kong
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
560-569
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）