### kostka's blog

By kostka, 2 years ago,

Hey Codeforces community,

have you ever seen any problems that use Wavelet Tree/Matrix or can be solved using these data structures?

Problems created especially for these structures don't count (for example they should appear in some competition).

• +72

 » 2 years ago, # |   +3 This Codeforces Div1-D problem. Solution using wavelet tree is described in this comment.
 » 2 years ago, # |   0 Min_25 solved this Codechef problem in $O(N\log^2 N)$ with 3D Wavelet Matrix. I'm not sure if that's the easiest way to achieve $O(N\log^2 N)$ though.
•  » » 2 years ago, # ^ |   0 Nevermind, it seems persistent trees also do the job :)
 » 2 years ago, # |   0 Wavelet Trees Tutorial it's turorial for wavelet trees and in comments there are some problems
 » 2 years ago, # |   +10 In the paper Wavelet Trees for Competitive Programming by Robinson Castro, Nico Lehmann, Jorge Perez and Bernardo Subercaseaux, three problems where wavelet trees are useful are introduced. These problems can also be solved with persistent segment trees, but wavelet trees have much lower memory usage.In general I think that all problems solvable with wavelet trees can also be solved with persistent or 2D segment trees. However the advantage of wavelet trees is lower memory usage. The reason why wavelet trees were invented in the first place was to create memory optimized data structures in bioinformatics, where strings like the human DNA are billions of characters long.
 » 2 years ago, # |   0 UTPC 2011 L (in Japanese) You are given a tree. Each node $v$ has a number $a_v$. For each query, you have to output the $L_q$th smallest number on the path from $v_q$ to $w_q$. $N,Q \leq 1e5, a_v \leq 1e9$.
 » 2 years ago, # |   0 #302 (Div 1) Problem E can be solved using Wavelet Matrix.