Near-Linear Preprocessing for Range Weighted Longest Increasing Subsequence Queries

Abstract

We give a deterministic data structure for range weighted longest increasing subsequence (LIS) queries on $n$ values with positive weights. Preprocessing takes $O(n{\log }^{2}n)$ time and space. Value queries take $O(\log n)$ time, and an optimal subsequence of $k$ elements can be reported in $O(k+\log n)$ time. This resolves an open question on truly subquadratic preprocessing with polylogarithmic query time. The key is a single-crossing property of envelopes for value-separated endpoint sets, enabling $O(\log n)$-time persistent merges. The bounds assume constant-time exact addition and comparison of weights.

8 pages, 1 figure