rachitjain's blog

By rachitjain, history, 5 months ago, In English,

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?

 
 
 
 
  • Vote: I like it  
  • +256
  • Vote: I do not like it  

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

What about "change an element" queries? If we solve the problem offline, they can be reduced to two "toggle" queries. But is it possible to solve it online? For example, by using order statistic tree instead of BIT?

Also can someone explain why this structure is called a "wavelet tree"?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Wikipedia:

    The name derives from an analogy with the wavelet transform for signals, which recursively decomposes a signal into low-frequency and high-frequency components.

»
5 months ago, # |
  Vote: I like it +51 Vote: I do not like it

Author sleeping since 32 hours

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Lol, I have just graduated from college and started off with a new job in a new place. So, I am busy with the new life and searching for flats which is tiring af.

»
5 months ago, # |
  Vote: I like it -92 Vote: I do not like it

This DS is called HBB PRO Tree. Why the fuck do you call it wavelet tree?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice blog post.

But I would like to add 1 and 2 can be done in O(logn) using regular segment tree if queries can be handled offline(and no updates).

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Maybe I can't get how the first problem can be solved using segment tree offline,could you please explain it in detail? Thanks!

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Keep 2 kinds of queries:
      1. (x,i) : The ith position is supposed to be assigned value x
      2. (x,l,r): Count number of elements in [l,r] which are less than x

      So obviously the queries are of the form (a[i],i) for i from 1 to n, and the range queries that we have. Now sort all the queries by x. Keep a segment tree over 1 to n. Initially, all the nodes have the value 0. Now whenever you encounter the first query, set the value at i to 1. For the second query the answer is just the number of 1's from l to r, which is a normal range sum query.

      You can see pretty easily that this works.

»
5 months ago, # |
  Vote: I like it +73 Vote: I do not like it

Is it correct that wavelet tree is conceptually just a merge-sort-like-tree built on top of values instead of positions?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not sure what you mean, but probably not. Haven't you mixed up "values" and "positions"?

    Wavelet tree was designed to overcome binary alphabet size limitation of succinct bit-vectors with constant-time rank and select queries. Thus the essence of wavelet trees is splitting the sequence over alphabet into series of bit-vectors in a balanced way. It certainly doesn't merge nor sorts anything.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      No, I did not.

      By "merge-sort-like-tree" I mean the following: suppose we have a standard segment tree over an array, but each node stores (instead of a fixed-size value) a sorted list of all values in the corresponding subtree. Here is an example for array 4 6 2 1 7 3 8 5:

      [1  2  3  4  5  6  7  8] - values on positions 1-8 (node 1)
      [1  2  4  6][3  5  7  8] - values on positions 1-4, 5-8 (nodes 2 and 3)
      [4  6][1  2][3  7][5  8] - values on positions 1-2, 3-4, 5-6, 7-8 (nodes 4-7)
      [4][6][2][1][7][3][8][5] - values on positions 1, 2, ..., 8 (nodes 8-15)
      

      That data structure can easily calculate number of elements less than X whose positions are between L and R in — just split [L;R] into nodes and run binary search inside each node. With fractional cascading we can reduce that time into by running binary search on the top level only.

      Wavelet tree does something similar: instead of looking at values

      (1, 4); (2, 6); (3, 2); (4, 1); (5, 7); (6, 3); (7, 8); (8, 5)
      

      it looks at

      (4, 1); (6, 2); (2, 3); (1, 4); (7, 5); (3, 6); (8, 7); (5, 8)
      similar to
      (1, 4); (2, 3); (3, 6); (4, 1); (5, 8); (6, 2); (7, 5); (8, 7)
      

      and builds something similar to the structure we had above: each node corresponds to a sub-segment of possible values and contains their sorted positions (we have no need to store the positions explicitly, we just pretend that they're here):

      [1  2  3  4  5  6  7  8] - positions of values 1-8 (node 1)
      [1  3  4  6][2  5  7  8] - positions of values 1-4, 5-8 (nodes 2-3)
      [3  4][1  6][2  8][5  7] - positions of values 1-2, 3-4, 5-6, 7-8 (nodes 4-7)
      [4][3][6][1][8][2][5][7] - positions of values 1, 2, ..., 8 (nodes 8-15)
      
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Seems like one could say that these data structures are transposed versions of each other.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Having come up with another solution to your three problems,we can use a persistent segment tree to deal with all three problems online(We can deal with 1 and 2 directly,and for problem 3,we can do binary search on the persistent segment tree which is still O(logn)).So we can have an alternative way to solve your three problems in O(nlogn) memory and time complexity.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain how binary search on segment tree would be O(logn)?

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Are you considering updates as well?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I haven't figured out how to do the "toogle" update with persistent segment tree — you have to actually update linear number of versions.

    Also, persistent segment tree is not, more strictly speaking, — it's memory and time, where n is the length of the array, m is the number of queries and V is the maximal value. By adding garbage collection we can reduce memory consumption to , but that makes code harder (and if you use standard pointer like shared_ptr it significantly increases hidden const).

    On the other hand, wavelet tree takes memory without garbage collection and time.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If we can compress values, persistent segment tree is . If we can't, wavelet tree is also .

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Fair enough. Is there any situation where we cannot compress values, but can build wavelet tree?

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For example, if we need to process online "push_back" updates.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't mean persistent segment tree is better than wavelet tree,and wavelet tree certainly does better in these kind of problems.I just point out that there exists an alternative way to solve these kind of problems.

      What's more,if we are asked to update values and even insert new values,we can use binary search tree without rotations(In China it's called Scape-Goat Tree) and segment tree to solve the problem in O(nlog^2n) time complexity.

      There is a problem of this kind which you're asked to ask queries of the k-th smallest element in a range as well as update and insert elements.

      Problem Link(in Chinese)

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        Would you mind elaborating what is Scape-Goat tree a little? Is it like segment tree for 109 leaves with dynamically allocated nodes?

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Scape-Goat Tree on Wikipedia

          Scape-Goat tree is a kind of binary search tree like Treap and Splay. But it makes itself balanced by reconstruction instead of rotation.Practically,if we find the size of the root's left son becomes larger than k*size of the tree or smaller than (1-k)*size of the tree,we just collect all its vertices and rebuild a new binary search tree.Usually k is set to be between 0.7 and 0.8.There is a proof why its complexity is O(nlogn) just as Treap and Splay.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Nice Substitute For Persistent Segment Tree.But how Can we add Update part to it?

»
5 months ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

Published version Direct link to the paper :)

As one of the authors of the paper, if anyone has any doubt about the structure, my mail is bernardosubercaseaux@gmail.com

Ps: A paper about how to answer the same querys in a Tree in an efficient and elegant way is going to be published soon ;)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is the complexity of solving 3rd problem from the blog using wavelet tree? Also, can it support updates?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You should read the paper :) the first question is answered in detail there. The answer for the simplest case when you have an array of N elements (in a reasonable alphabet, for example, numbers < 10^9) is O(lg(N)) per query.

      For the updates, in the paper we covered some cases, like toggling, adjacent-swapping, push_back and push_front.

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Hi, I'm trying to use wavelet tree for MKTHNUM problem on SPOJ, but I keep getting runtime error.

Can anyone tell me what's wrong with my submission? Code

I used the template and just changed the main function.