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

# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

5 | Ashishgup | 182 |

6 | vovuh | 181 |

7 | Um_nik | 179 |

8 | Radewoosh | 174 |

9 | SecondThread | 172 |

10 | McDic | 161 |

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/03/2020 18:49:08 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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.

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

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

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.

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

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