Encodings of range maximum-sum segment queries and applications

DOI10.1007/978-3-319-19929-0_17MaRDI QIDQ2942257zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Patrick K. Nicholson

Publication date 20 August 2015

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.2847

Mathematics Subject Classification ID

Data structures (68P05) Database theory (68P15)

Abstract: 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 of the numbers in A[i'..j'] is maximized. Chen and Chao [Disc. App. Math. 2007] presented a data structure for this problem that occupies {Theta}(n) words, can be constructed in {Theta}(n) time, and supports queries in {Theta}(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 {Theta}(n) bits, regardless the numbers stored in A, while retaining the same construction and query time. We also improve the best known space lower bound for any data structure that supports range maximum-sum segment queries from n bits to 1.89113n - {Theta}(lg n) bits, for sufficiently large values of n. Finally, we provide a new application of this data structure which simplifies a previously known linear time algorithm for finding k-covers: i.e., 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.

Recommendations

• Algorithms and Computation
• On the range maximum-sum segment query problem
• An optimal algorithm for maximum-sum segment and its application in bioinformatics (extended abstract)
• Optimal encodings for range top-\(k\), selection, and min-max
• Algorithms and Computation

Cites work

• A simple optimal representation for balanced parentheses
• Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
• Array range queries
• Computing Maximum-Scoring Segments in Almost Linear Time
• Data structures for efficient string algorithms.
• Encodings of range maximum-sum segment queries and applications
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• On the range maximum-sum segment query problem
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Succinct representation of balanced parentheses and static trees
• Time bounds for selection

Cited in

(5)

• Encoding two-dimensional range top-\(k\) queries
• Encodings of range maximum-sum segment queries and applications
• Encoding two-dimensional range top-k queries revisited
• An encoding for order-preserving matching
• Algorithms and Computation

This page was built for publication: Encodings of range maximum-sum segment queries and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942257)