Introduction to New Data Structure: Wavelet Trees

Revision en3, by rachitiitr, 2017-06-24 10:35:27

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 kth 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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English rachitiitr 2017-06-24 10:35:27 64
en2 English rachitiitr 2017-06-24 10:28:55 37
en1 English rachitiitr 2017-06-23 23:57:43 1045 Initial revision (published)