Given an array A[1 : n] of n elements drawn from an ordered set, the sorted range selection problem is to build a data structure that can be used to answer following queries: Given a pair of indices i, j \( (1\le i\le j \le n)\) , and a positive integer k, report the k smallest elements from the sub-array A[i : j] in sorted order. Brodal et al. (Brodal, G. S., Fagerberg, R., Greve, M., and López-Ortiz, A., Online sorted range reporting. Algorithms and Computation (2009) pp. 173–182) introduced the problem and gave a solution that can answer a query in O(k) time. The preprocessing takes \(O(n\log n)\) time and O(n) space. In this paper, we propose the only other possible optimal trade-off for the problem. After preprocessing using O(n) time and space, we can answer a range selection query in \(O(k\log k)\) time. Moreover, the proposed algorithm reports the output elements individually in non-decreasing order. Our solution is simple and practical. We also study the problem in a dynamic setting. We also describe an extremely simple method for the range minima queries (most of whose parts are known), which takes almost (but not exactly) linear time. We believe that this method may be, in practice, faster and easier to implement in most cases. Moreover, we also give a simple dynamic solution to the range minimum problem.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Sorted Range Selection and Range Minima Queries

  • Waseem Akram,
  • Sanjeev Saxena

摘要

Given an array A[1 : n] of n elements drawn from an ordered set, the sorted range selection problem is to build a data structure that can be used to answer following queries: Given a pair of indices i, j \( (1\le i\le j \le n)\) , and a positive integer k, report the k smallest elements from the sub-array A[i : j] in sorted order. Brodal et al. (Brodal, G. S., Fagerberg, R., Greve, M., and López-Ortiz, A., Online sorted range reporting. Algorithms and Computation (2009) pp. 173–182) introduced the problem and gave a solution that can answer a query in O(k) time. The preprocessing takes \(O(n\log n)\) time and O(n) space. In this paper, we propose the only other possible optimal trade-off for the problem. After preprocessing using O(n) time and space, we can answer a range selection query in \(O(k\log k)\) time. Moreover, the proposed algorithm reports the output elements individually in non-decreasing order. Our solution is simple and practical. We also study the problem in a dynamic setting. We also describe an extremely simple method for the range minima queries (most of whose parts are known), which takes almost (but not exactly) linear time. We believe that this method may be, in practice, faster and easier to implement in most cases. Moreover, we also give a simple dynamic solution to the range minimum problem.