Hi everybody,

If you can recall, I had written a tutorial for a relatively new Data Structure: Wavelet Trees.

The link to that post is here.

Consider the following problems:

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

(Persistence Segment Tree? Ordered multiset + BIT ?) - Number of occurrences of element x in subarray A[L...R].

(Subpart of 1st problem) - 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 Awesome, isn’t it?

I have made a video tutorial for the same. Check out the video here.

Video — Wavelet Trees | Introduction to New Data Structure

Youtube Channel ► http://www.youtube.com/c/RachitJain

Facebook Page ► http://fb.me/LearningAlgorithmsWithRachitJain

Competitive Programming Blog ► http://rachitiitr.blogspot.com

CodeForces ► http://www.codeforces.com/profile/rachitjain

CodeChef ► http://www.codechef.com/users/rachitiitr

Happy Coding!