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!