WaveletMatrix

Back
Language: ruby
License: CC0 1.0
Prefix: wm
Description:
  • initialize(array): 配列からWaveletMatrixを構築する
  • access(k): k番目(0-indexed)の要素の値を返す
  • kth_smallest(l, r, k): 区間[l, r)内のk番目(0-indexed)に小さい値を返す
  • kth_largest(l, r, k): 区間[l, r)内のk番目(0-indexed)に大きい値を返す
  • range_freq(l, r, upper): 区間[l, r)内のupper未満の要素の個数を返す
  • prev_value(l, r, upper): 区間[l, r)内のupper未満の最後の値を返す
  • next_value(l, r, lower): 区間[l, r)内のlower以上の最初の値を返す
  • count(l, r, x): 区間[l, r)内のxの出現回数を返す
  • sum_less_than_x(l, r, upper): 区間[l, r)内のupper未満の要素の総和を返す
Verified Links
https://judge.yosupo.jp/submission/2608332025/01/09
https://atcoder.jp/contests/abc339/submissions/615071272025/01/10