2026-10-01T07:51:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26059 2026-09-23T23:59:09Z ddc:004 open_access

Indexing Range Maximum-Sum Segment Queries with Offsets Jo, Seungbum Köppl, Dominik maximum segment sum data structure range query 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Seungbum Jo and Dominik Köppl 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.23 urn:nbn:de:0030-drops-260597 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.23 eng https://creativecommons.org/licenses/by/4.0/legalcode