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

Unable to parse markup [type=CF_TEX]

that are less than or equal to

Unable to parse markup [type=CF_TEX]

.
(Persistence Segment Tree? Ordered multiset + BIT ?)
2. Number of occurrences of element x in subarray

Unable to parse markup [type=CF_TEX]

.
(Subpart of 1st problem)
3. The

Unable to parse markup [type=CF_TEX]

smallest element in subarray

Unable to parse markup [type=CF_TEX]

.
(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?

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?