...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On the range maximum-sum segment query problem
【24h】

On the range maximum-sum segment query problem

机译：关于范围最大和段查询问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The range minimum query problem, RMQ for short, is to preprocess a sequence of real numbers A[1... n] for subsequent queries of the form: "Given indices i,j, what is the index of the minimum value of A[i... j]?" This problem has been shown to be linearly equivalent to the LCA problem in which a tree is preprocessed for answering the lowest common ancestor of two nodes. It has also been shown that both the RMQ and LCA problems can be solved in linear preprocessing time and constant query time under the unit-cost RAM model. This paper studies a new query problem arising from the analysis of biological sequences. Specifically, we wish to answer queries of the form: "Given indices i and j, what is the maximum-sum segment of A[i... j]?" We establish the linear equivalence relation between RMQ and this new problem. As a consequence, we can solve the new query problem in linear preprocessing time and constant query time under the unit-cost RAM model. We then present alternative linear-time solutions for two other biological sequence analysis problems to demonstrate the utilities of the techniques developed in this paper. (C) 2007 Elsevier B.V. All rights reserved.
机译：范围最小查询问题，简称RMQ，是对一系列实数A [1 ... n]进行预处理，以便随后进行以下形式的查询：“给出索引i，j，A的最小值的索引是多少？ [i ... j]？”该问题在线性上等效于LCA问题，在该问题中，对树进行预处理以回答两个节点的最低共同祖先。还表明，在单位成本RAM模型下，RMQ和LCA问题都可以在线性预处理时间和恒定查询时间中解决。本文研究了由生物学序列分析引起的新查询问题。具体来说，我们希望回答以下形式的查询：“给定索引i和j，A [i ... j]的最大和段是多少？”我们建立了RMQ与这个新问题之间的线性等价关系。因此，我们可以在单位成本RAM模型下以线性预处理时间和恒定查询时间解决新的查询问题。然后，我们针对其他两个生物学序列分析问题提出了替代的线性时间解决方案，以证明本文开发的技术的实用性。 （C）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号