### rachitiitr's blog

By rachitiitr, history, 5 years ago,

Hi CF Community,

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?

• +256

 » 5 years ago, # |   +6 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 years ago, # ^ |   +6 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 years ago, # |   +51 Author sleeping since 32 hours
•  » » 5 years ago, # ^ |   +17 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 years ago, # |   -92 This DS is called HBB PRO Tree. Why the fuck do you call it wavelet tree?
 » 5 years ago, # |   0 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 years ago, # ^ |   +5 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 years ago, # ^ |   +10 Keep 2 kinds of queries:1. (x,i) : The ith position is supposed to be assigned value x2. (x,l,r): Count number of elements in [l,r] which are less than xSo 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 years ago, # ^ |   +5 Got it,thanks a lot!
•  » » » » » 5 years ago, # ^ |   +10 See this link for more details — https://www.quora.com/How-will-you-solve-the-K-Query-using-segment-trees
 » 5 years ago, # |   +73 Is it correct that wavelet tree is conceptually just a merge-sort-like-tree built on top of values instead of positions?
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   +15 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) 
•  » » » » 5 years ago, # ^ |   0 Seems like one could say that these data structures are transposed versions of each other.
 » 5 years ago, # |   0 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 years ago, # ^ |   0 Could you explain how binary search on segment tree would be O(logn)?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Are you considering updates as well?
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 If we can compress values, persistent segment tree is . If we can't, wavelet tree is also .
•  » » » » 5 years ago, # ^ |   0 Fair enough. Is there any situation where we cannot compress values, but can build wavelet tree?
•  » » » » » 5 years ago, # ^ |   0 For example, if we need to process online "push_back" updates.
•  » » » 5 years ago, # ^ |   0 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)
•  » » » » 5 years ago, # ^ |   +15 Would you mind elaborating what is Scape-Goat tree a little? Is it like segment tree for 109 leaves with dynamically allocated nodes?
•  » » » » » 5 years ago, # ^ |   +5 Scape-Goat Tree on WikipediaScape-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.
•  » » » » 4 years ago, # ^ |   0 Could you please elaborate how would we solve this problem with segment tree and space-goat tree?
 » 5 years ago, # | ← Rev. 2 →   0 Nice Substitute For Persistent Segment Tree.But how Can we add Update part to it?
 » 5 years ago, # | ← Rev. 2 →   +31 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.comPs: 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 years ago, # ^ |   0 What is the complexity of solving 3rd problem from the blog using wavelet tree? Also, can it support updates?
•  » » » 5 years ago, # ^ |   0 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 years ago, # |   +4 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? CodeI used the template and just changed the main function.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 i also copied those code too, but getting wrong answer instead. here is my submission ideone
•  » » » 5 years ago, # ^ |   +4 Have you used index compression? The numbers can be up to 10^9
•  » » » » 5 years ago, # ^ |   +1 thanks, i use index compression and got AC. I safely assume RTE in your submission is not related about the DS.
•  » » » » » 5 years ago, # ^ |   0 Can you please share your code , as i am not able to find the bug.raidnav
•  » » » » » » 5 years ago, # ^ |   0
•  » » » » 4 years ago, # ^ |   0 does compression matter for getting the correct output?
•  » » » » » 4 years ago, # ^ |   0 Compression is needed due to the input constraint that can be up to 10^9. I don't think you can make any array of that size without compressing the value first..
•  » » » 5 years ago, # ^ |   0 you can try with the implementation referenced in the paper https://github.com/nilehmann/wavelet-tree/also, for those of you lazy enough to not read the paper ;-) you can check the following slides for a quick view of how the WT workshttps://users.dcc.uchile.cl/~jperez/talks/ioi16.pdf
•  » » » 5 years ago, # ^ |   0 I also tried the same problem and im getting WA. I implemented by myself but I compared with some other codes and seems pretty much the same. Can anyone help me? code
 » 4 years ago, # |   0 Is it possible to support the following type of update using wavelet tree?Given l, r, x, add x to all the elements from al to ar.
•  » » 4 years ago, # ^ |   0 Searching for same....
 » 4 years ago, # |   0 Is It possible to delete Element Or Update the Value of element ?
•  » » 4 years ago, # ^ |   0 Yes, but you have to use something else instead of arrays to store the bitarray for efficiencyI used a bst here
 » 3 years ago, # |   0 I wonder if there is something that this can do but ordered multiset+seg tree can't ? P.S. I found coding seg tree much easier than this new data structure.
 » 23 months ago, # | ← Rev. 3 →   0 It would be great if you (rachitiitr)can write another blog explaining about Wavelet Trees.
 » 22 months ago, # |   +6 Link is broken :(
•  » » 22 months ago, # ^ |   +12 Looks like this works.
•  » » » 22 months ago, # ^ |   0 Thanks!
 » 22 months ago, # | ← Rev. 3 →   +9 I don't actually know the English name but there is indeed a similar data structure in China, called “主席树” or HJT seg-tree, and there are a bunch of problems like that in China.The main idea was to save a single-point change of a segment tree in $O(\log n)$ memory & time complexity.First, we do discretization for all numbers.Second, we build an empty seg-tree with the size of n, we'll let it be version[0].Then we let i from 1 to n, we make the element in place a[i] $+1$ and make a new version i (based on version[i-1])Similar to prefix, all data of numbers in $a_l$ to $a_r$ will be in version[r]-version[l-1], we can than perform these operations in $O(\log n)$ time.The total complexity will be $O(n\log n+q\log n)$