arXiv preprint ·
Near-Linear Preprocessing for Range Weighted Longest Increasing Subsequence Queries
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage
A 0.4584-approximation for DR-submodular maximization over down-closed convex sets
Revisiting Non-Adaptive Set Membership Schemes: Removing the Logarithmic Factor
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.