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

hamayanhamayan's blog

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

累積和・imos法

  • 累積和
    • 累積の和をとっておくと、区間の総和がO(1)で取得できる 参考
    • 累積和は、先頭からの和だけでなく、先頭からの積・先頭からのgcdも可能である。交換則も必要ないので、行列に対しての計算も可能である
    • 二次元に拡張することもできる
  • imos法
    • 一定区間にある数を足すクエリを仕込みO(1),後処理O(N)で行う方法 本家解説
    • 普通は0次1次元であるが、高次高次元に拡張できる(らしい)