pipette
ENEnglish

Near-Linear Preprocessing for Range Weighted Longest Increasing Subsequence Queries

Keisuke Korogi

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 8 pages, 1 figure