kostka's blog

Wavelet tree problems
By kostka, 5 years ago, In English

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).

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

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This Codeforces Div1-D problem. Solution using wavelet tree is described in this comment.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    Nevermind, it seems persistent trees also do the job :)

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wavelet Trees Tutorial it's turorial for wavelet trees and in comments there are some problems

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

#302 (Div 1) Problem E can be solved using Wavelet Matrix.

→ Reply