I recently learned wavelet trees. This data structure can handle the following types of range queries in logarithmic time:
- Number of elements in subarray A[L...R] that are less than or equal to y.
- Number of occurrences of element x in subarray A[L...R].
- 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.com/blog/entry/52854
