Блог пользователя kostka

Автор kostka, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится 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$$$.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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