[Video Tutorial] Introduction to Wavelet Trees: Simple, Clean Yet Powerful

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:

  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 :smiley: 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!


how to do point update in wavelet tree…