Wavelet Tree Implementation(Array Based)

Revision en1, by thisIsMorningstar, 2023-02-24 14:58:09

I recently learned wavelet trees. This data structure can handle the following types of range queries in logarithmic time:

  1. Number of elements in subarray A[L...R] that are less than or equal to y.
  2. Number of occurrences of element x in subarray A[L...R].
  3. The kth smallest element in subarray A[L...R].

But I couldn't find the array based implementation of it anywhere, and as I don't like pointers(also pointer based implementations are often slower than array based ones because of the dynamic memory allocation), I implemented it myself. Here is the implementation: https://github.com/thisIsMorningstar/Competitive_Programming/blob/main/templates/wavelet_tree.cpp

I stress tested this with a bruteforce code against a couple thousand random testcases and it passed. But if you find any bugs in it, do let me know :).

You can learn about wavelet trees from here: https://codeforces.net/blog/entry/52854

Tags wavelet tree, data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English thisIsMorningstar 2023-02-24 14:58:09 965 Initial revision (published)