Near-Linear Preprocessing for Range Weighted Longest Increasing Subsequence Queries
In the authors' words
We give a deterministic data structure for range weighted longest increasing subsequence (LIS) queries on values with positive weights. Preprocessing takes time and space. Value queries take time, and an optimal subsequence of elements can be reported in 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 -time persistent merges. The bounds assume constant-time exact addition and comparison of weights.
Main resultLimitation the authors admit
Appeared: Friday, October 16. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 8 pages, 1 figure