Hi CF Community,

http://rachitiitr.blogspot.in/2017/06/wavelet-trees-wavelet-trees-editorial.html

I think it's safe to assume that this is a new data structure for most of us.

Consider the following problems:

1. Number of elements in subarray *A*[*L*...*R*] that are less than or equal to *y*.

(Persistence Segment Tree? Ordered multiset + BIT ?)

2. Number of occurrences of element *x* in subarray *A*[*L*...*R*].

(Subpart of 1st problem)

3. The *k*^{th} smallest element in subarray *A*[*L*...*R*].

(Ordered multiset + BIT would work for subarrays beginning from index 1)

I know you might have many other solutions, and you might think what I am trying to prove.

What if I told you, all of the above can be easily done in O(logn) using Wavelet Trees :o. Plus, its very easy to code :D Awesome, isn't it?

Check the implementation here.

The post just introduces the basic usage of wavelet trees. There is still more that you can do with them.

I will write about them later, once I gain enough sleep maybe?