2026/01/01 by Seungbum Jo, Dominik Köppl
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation
paper · pdf · doi:10.4230/lipics.swat.2026.23
Given an array of n real numbers, the maximum segment sum (MSS) problem is to find a contiguous subarray that has the largest sum. While the MSS problem can be solved optimally with Kadane’s algorithm in O(n) time, the study of its indexing version spawned new extensions such as (a) retrieving the MSS after subtracting a query offset parameter for all array entries or (b) retrieving the MSS for arbitrary query ranges. We here study the combination of both problems (a) and (b), which requires retrieving the MSS for arbitrary query ranges after subtracting a query offset parameter for all array entries. For that, we present an index whose query time is only slower than the best known for (a) by a factor of O(log n). In detail, our index uses O(n log n) space, supports queries in O(log² n) time, and can be constructed in O(n log³ n) time. As side results, we study our combined problem in the context of run-length compressed input, and also deduce a solution for (a) that works in run-length compressed space and time. Finally we give supportive lower bounds for our query problem, showing that there is only a polylogarithmic gap of improvement left.