pipette
ESEspañol

Near-Linear Preprocessing for Range Weighted Longest Increasing Subsequence Queries

Keisuke Korogi

Preprint

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