{"id":24826,"library":"wavelet-matrix","title":"wavelet-matrix","description":"A high-performance indexed sequence data structure powered by Rust, supporting fast rank/select and range queries. Current version 2.1.8, requires Python >=3.9. Released under MIT license; maintained by wm-team.","status":"active","version":"2.1.8","language":"python","source_language":"en","source_url":"https://github.com/wm-team/wavelet-matrix","tags":["data-structures","rust","rank-select","wavelet-tree","indexed-sequence"],"install":[{"cmd":"pip install wavelet-matrix","lang":"bash","label":"Install from PyPI"}],"dependencies":[],"imports":[{"note":"Hyphen in package name, underscore in import module name.","wrong":"from waveletmatrix import WaveletMatrix","symbol":"WaveletMatrix","correct":"from wavelet_matrix import WaveletMatrix"}],"quickstart":{"code":"from wavelet_matrix import WaveletMatrix\ndata = [5, 3, 1, 4, 2]\nwm = WaveletMatrix(data)\nprint(wm.rank(3, 2))  # rank of value 3 up to index 2\nprint(wm.select(1, 1))  # position of the 1st occurrence of value 1\nprint(wm.quantile(0, 4, 2))  # 2nd smallest in range [0,4]","lang":"python","description":"Basic usage: create a WaveletMatrix from a list of integers, then use rank, select, and quantile methods."},"warnings":[{"fix":"Remove the second argument from constructor: `WaveletMatrix(data)`.","message":"In version 2.0, the constructor argument order changed from `data, alphabet_size` to `data` only, with automatic alphabet detection. Code using `WaveletMatrix(data, 256)` will raise TypeError.","severity":"breaking","affected_versions":">=2.0.0"},{"fix":"Ensure indices are 0-based. For 1-based indexing, adjust by -1.","message":"Rank and select methods are 0-indexed. `rank(value, index)` returns count of `value` up to and including the position `index`. `select(value, k)` returns the 0-based position of the kth occurrence (k is 0-based).","severity":"gotcha","affected_versions":"all"},{"fix":"Map your data to non-negative integers before constructing the WaveletMatrix.","message":"The library only supports non-negative integers up to 2^31-1. Negative numbers or floats will raise TypeError or overflow.","severity":"gotcha","affected_versions":"all"}],"env_vars":null,"last_verified":"2026-05-01T00:00:00.000Z","next_check":"2026-07-30T00:00:00.000Z","problems":[{"fix":"Use `from wavelet_matrix import WaveletMatrix` (note underscore).","cause":"Importing using the package name with hyphen instead of underscore.","error":"AttributeError: module 'wavelet_matrix' has no attribute 'WaveletMatrix'"},{"fix":"Call `WaveletMatrix(data)` without alphabet size. The class now infers alphabet automatically.","cause":"Passing the old second argument (alphabet_size) to constructor.","error":"TypeError: WaveletMatrix.__init__() got multiple values for argument 'data'"},{"fix":"Ensure index < len(wavelet_matrix). Rank indices are 0-based up to n-1.","cause":"Passing an index >= length of the sequence.","error":"ValueError: Rank query index out of range"}],"ecosystem":"pypi","meta_description":null,"install_score":null,"install_tag":null,"quickstart_score":null,"quickstart_tag":null}