いもす法

• 配列のある範囲に同じ値を加算する

  • $A_i\leftarrow A_i+X[s\le i<e]$ where s: start, e: end
  • このクエリがQ回行われる
  • 素朴に実装するとO(NQ)
  • 先に範囲の開始と終了だけを加算する
  • $B_i\leftarrow B_i+X[i=s]-X[i=e]$
  • その後、累積和を取れば同じものが得られる: O(N+Q)
  • $A_i\leftarrow A_{i-1}+B_i$
  • 微分の形で計算しておいて最後に積分する感じ

• いもす法 - いもす研 (imos laboratory)

  • 累積和のアルゴリズムを多次元，多次数に拡張したもの

• 累積和といもす(imos)法 - Qiita

https://maspypy.com/atcoder-参加感想-2019-02-16abc-155

atcoder Range Add