search

kth-competitive-programming / kactl

KTH Algorithm Competition Template Library (... eller KTHs AC-tillverkande lapp)
2.69k stars 711 forks source link

Add wavelet tree #200

Open hockyy opened 3 years ago

hockyy commented 3 years ago

https://gitlab.au.dk/BeyondBallmersPeak/kactl/-/blob/4fde3a49533621e4178d8dffa29bf0701fe8f8db/content/data-structures/WaveletTree.h

Here is a good implementation of it.

Here is another good implementation https://usaco.guide/problems/kattis-easy-query/solution

BarrensZeppelin commented 3 years ago

Beware that my implementation actually uses O(M + N log M) space (where M is the difference between the smallest and largest elements), because it constructs a complete tree with M leaves. It can be reduced to N log M by constructing the tree lazily, but the operations will require a little more code.

Also, the quantile query is the only interesting query IMO. Rank and rectangle queries are just as easily answered by other trees such as persistent segment trees.

simonlindholm commented 3 years ago

Quantile can also be done with persistent segment trees: recurse on the segtrees for L and R together, descend to the left if k < L->left->sum + R->left->sum else to the right. As I see it wavelet trees and persistent segtrees are basically isomorphic, they just store pointers differently. The only reason to use wavelet trees is if you were able to combine it with another data structure (e.g. I'm not sure off hand how to solve the "toggle" queries described in https://users.dcc.uchile.cl/~jperez/papers/ioiconf16.pdf with persistent segtrees), or if you used a bit-compressed version to save a factor ~32 on memory usage.

https://codeforces.com/profile/nor helpfully links to https://judge.yosupo.jp/submission/60640 as a nice bit-compressed version. It also stores bits for each of the log M layers consecutively ("wavelet matrix"), which makes them dense even at the leaves and avoids some memory indirection. It's very long though.