はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるWaveletMatrix問題まとめ

WaveletMatrix

  • WaveletTreeというのもあるが、WMは完全上位互換らしいので、こっちを使えるようになろう
  • (ウェーブレット行列は静的なものだが、動的にもできるし、永続化もできる)←どこを見て書いたんだろう
  • 解説
  • 実装例 antaさん Algoogleさん
  • できること
    • quantile: 降順ソートしたときにk番目に大きい数を取ってくる
    • freqency: ある区間内にある範囲の数が何個あるか
    • 区間に含まれるk番目のvの位置も取れるらしい [beetさんの強ライブラリ](区間に含まれるvの数、区間に含まれるk番目のvの位置、区間内でk番目に大きい要素)
    • 重複要素を無視して、k番目に大きい数も取ってこれるテク