いもす法
配列のある範囲に同じ値を加算する
$ A_i ← A_i + X[s \le i < e]
where s: start, e: end
このクエリがQ回行われる
素朴に実装するとO(NQ)
先に範囲の開始と終了だけを加算する
$ B_i ← B_i + X[i = s] - X[i=e]
その後、
累積和
を取れば同じものが得られる: O(N+Q)
$ A_i ← A_{i-1} + B_i
微分の形で計算しておいて最後に積分する感じ
いもす法 - いもす研 (imos laboratory)
累積和
のアルゴリズムを多次元，多次数に拡張したもの
累積和といもす(imos)法 - Qiita
https://maspypy.com/atcoder-参加感想-2019-02-16abc-155
atcoder
Range Add