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

hamayanhamayan's blog

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

累積和

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

問題

1次元累積和

2次元累積和

imos法

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