On the Range Maximum-Sum Segment Query Problem

摘要

We are given a sequence A of n real numbers which is to be preprocessed. In the Range Maximum-Sum Segment Query (RMSQ) problem, a query is comprised of two intervals [i,j] and [k,l] and our goal is to return the maximum-sum segment of A whose starting index lies in [i,j] and ending index lies in [k,l].We propose the first known algorithm for this problem in O(n) preprocessing time and O(1) time per query under the unit-cost RAM model. We also use the RMSQ techniques to solve three relevant problems in linear time. These variations on the basic theme demonstrate the utilities of the techniques developed in this paper.