Succinct data structures for searchable partial sums with optimal worst-case performance
From MaRDI portal
Publication:719256
DOI10.1016/j.tcs.2011.05.023zbMath1226.68032OpenAlexW2055070832MaRDI QIDQ719256
Wing-Kai Hon, Wing-Kin Sung, Kunihiko Sadakane
Publication date: 10 October 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.023
Related Items
Compressed Data Structures for Dynamic Sequences, Compressed property suffix trees, Random access in persistent strings and segment selection, Unnamed Item, A faster implementation of online RLBWT and its application to LZ77 parsing, Succinct Partial Sums and Fenwick Trees, Approximate query processing over static sets and sliding windows, Dynamic relative compression, dynamic partial sums, and substring concatenation, Unnamed Item, Unnamed Item, Partial sums on the ultra-wide word RAM, Improved Space Efficient Algorithms for BFS, DFS and Applications, Space efficient linear time algorithms for BFS, DFS and applications, Faster online computation of the succinct longest previous factor array, Succinct dynamic cardinal trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal bounds for the predecessor problem and related problems
- Rank and select revisited and extended
- Space Efficient Suffix Trees
- Low Redundancy in Static Dictionaries with Constant Query Time
- Succinct Representation of Balanced Parentheses and Static Trees
- Compressed representations of sequences and full-text indexes
- Indexing compressed text
- Membership in Constant Time and Almost-Minimum Space
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Logarithmic Lower Bounds in the Cell-Probe Model
