首页> 外文期刊>Algorithmica >Optimal Encodings for Range Majority Queries
【24h】

Optimal Encodings for Range Majority Queries

机译:范围多数查询的最佳编码

获取原文
获取原文并翻译 | 示例

摘要

We study the problem of designing a data structure that reports the positions of the distinct iota-majorities within any range of an array A[1, n], without storing A. A iota-majority in a range A[i, j], for 0 < iota < 1, is an element that occurs more than iota(j - i + 1) times in A[i, j]. We show that Omega (n inverter right perpendicular log(1/iota) inverter left perpendicular) bits are necessary for any data structure just able to count the number of distinct iota-majorities in any range. Then, we design a structure using O (n inverter right perpendicular log(1/iota) inverter left perpendicular) bits that returns one position of each iota-majority of A[i, j] in O((1/iota) log log(w) (1/iota) log n) time, on a RAM machine with word size w (it can output any further position where each iota-majority occurs in Omicron(1) additional time). Finally, we show how to remove a log n factor from the time by adding Omicron(n log log n) bits of space to the structure.
机译:我们研究了设计一个数据结构的问题,该数据结构报告了数组A [1,n]的任意范围内不同iota多数的位置,而不存储A。Aota多数在范围A [i,j]中,对于0

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号