Overview
A wavelet tree recursively partitions values and stores bitvectors that guide queries through value ranges.
SpecializedSource checked
Wavelet Tree
Indexes sequences so rank, select, and range queries can be answered compactly.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Advanced
- Family
- Succinct Range Query Structure
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
rank queryselect queryvalue partitionbitvector
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log sigma)
Average
O(log sigma)
Worst
O(log sigma)
Space
O(n log sigma)
When to Use
- Use when fast lookup needs rank query.
- Use when the input matches the assumptions behind succinct Range Query Structure.
When Not to Use
- Avoid when the operation mix does not benefit from the structure's maintenance cost.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Indexes sequences so rank, select, and range queries can be answered compactly
- Uses rank query and select query to guide the work.
- Produces stored structure.
Use Cases
- Fast lookup
- Maintaining ordered data
- Representing graphs or spatial data
Inputs
- Items
- Keys or indexes
- Operations to support
Outputs
- Stored structure
- Query results
- Updated state
Key Formulas (1)
Rank step
rankc(prefix) follows bitvector rank into child node
rank_c(prefix) follows bitvector rank into child nodeUses bitvector ranks to map a query range to the next level.
Pseudocode
- 1.Prepare the inputs and state needed for Wavelet Tree.
- 2.Apply the rank query step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return stored structure.
Canonical Example
- Input
- Wavelet Tree input with a small representative case
- Output
- Stored structure
- Explanation
- Wavelet Tree applies rank query to produce stored structure.
Implementation Notes
- Test insertion, deletion, lookup, and boundary cases separately.
- Keep the rank query step separate enough to test independently.
Common Pitfalls
- Ignoring update costs can make a structure look faster than it is in practice.
- Forgetting to check edge cases can make Wavelet Tree look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the structure layout and how operations move through or update it.
Step 1 of 4: Prepare the inputs and state needed for Wavelet Tree.
data-structures-mechanismNotes
Wavelet Tree should be used with the assumptions and tradeoffs of succinct Range Query Structure in mind.
Sources (1)
What each reference supports for this entry.
Compact Data Structures
BookSuccinct data-structures reference for wavelet trees, rank/select support, and range queries over sequences.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborSuffix Array
Wavelet trees and suffix arrays are compact indexed structures that support sequence queries.
Related Algorithms
Tags
Data StructureRange QueryStringsCompression