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]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]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]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.