Encodings of Range Maximum-Sum Segment Queries and Applications

Given an array \(A\) containing arbitrary (positive and negative) numbers, we consider the problem of supporting range maximum-sum segment queries on \(A\): i.e., given an arbitrary range \([i,j]\), return the subrange \([i',j'] \subseteq [i,j]\) such that the sum \(\sum _{k=i'}^{j'} A[k]\) is maximized. (We use the terms segment and subrange interchangeably, but only use segment when referring to the name of the problem, for consistency with prior work.) Chen and Chao [Disc. App. Math. 2007] presented a data structure for this problem that occupies \(\varTheta (n)\) words, can be constructed in \(\varTheta (n)\) time, and supports queries in \(\varTheta (1)\) time. Our first result is that if only the indices \([i',j']\) are desired (rather than the maximum sum achieved in that subrange), then it is possible to reduce the space to \(\varTheta (n)\) bits, regardless the numbers stored in \(A\), while retaining the same construction and query time. Our second result is to improve the trivial space lower bound for any encoding data structure that supports range maximum-sum segment queries from \(n\) bits to \(1.89113n - \varTheta (\lg n)\), for sufficiently large values of \(n\). Finally, we also provide a new application of this data structure which simplifies a previously known linear time algorithm for finding \(k\)-covers: given an array \(A\) of \(n\) numbers and a number \(k\), find \(k\) disjoint subranges \([i_1 ,j_1 ],...,[i_k ,j_k]\), such that the total sum of all the numbers in the subranges is maximized. As observed by Csürös [IEEE/ACM TCBB 2004], \(k\)-covers can be used to identify regions in genomes.