- Implementation of Predecessor and Range Minimum Queries.
- Predecessor queries are implemented using Elias Fano coding using succinct bit vector data structure with rank/select query support.
- For RMQ three different data structures with O(N^2), O(NlogN) and O(N) time and space complexities are used.
- To achieve linear complexity in RMQ, input array is divided into subblocks, and encoded using the corresponding cartesian tree of the block.
-
Notifications
You must be signed in to change notification settings - Fork 0
KtrauM/predecessor-rmq
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
About
No description, website, or topics provided.
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published