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

hamayanhamayan's blog

競技プログラミングにおけるimos法・累積和問題まとめ

累積和

  • 累積の和をとっておくと、区間の総和がO(1)で取得できる 参考
  • 二次元に拡張することもできる

問題

1次元累積和
2次元累積和

imos法

  • 一定区間にある数を足すクエリを仕込みO(1),後処理O(N)で行う方法 本家解説
  • 普通は0次1次元であるが、高次高次元に拡張できる(らしい)

問題

0次1次元(一般的なimos法)

0次2次元(2次元imos法)

1次1次元(2回imos法を回すらしい)

より複雑なもの