<ul>
<li>配列のある範囲に同じ値を加算する
<ul>
<li>$A_i ← A_i + X[s \le i &lt; e]$ where s: start, e: end</li>
<li>このクエリがQ回行われる</li>
<li>素朴に実装するとO(NQ)</li>
<li>先に範囲の開始と終了だけを加算する</li>
<li>$B_i ← B_i + X[i = s] - X[i=e]$</li>
<li>その後、<a href="/ja/%E7%B4%AF%E7%A9%8D%E5%92%8C">累積和</a>を取れば同じものが得られる: O(N+Q)</li>
<li>$A_i ← A_{i-1} + B_i$</li>
<li>微分の形で計算しておいて最後に積分する感じ</li>
</ul>
</li>
<li><a href="https://imoz.jp/algorithms/imos_method.html">いもす法 - いもす研 (imos laboratory)</a>
<ul>
<li><blockquote>
<a href="/ja/%E7%B4%AF%E7%A9%8D%E5%92%8C">累積和</a>のアルゴリズムを多次元，多次数に拡張したもの
</blockquote>
</li>
</ul>
</li>
<li><a href="https://qiita.com/DaikiSuyama/items/67547e14b47cd6360252">累積和といもす(imos)法 - Qiita</a>
</li>
</ul>
<a href="https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-02-16abc-155">https://maspypy.com/atcoder-参加感想-2019-02-16abc-155</a>
<a href="/ja/atcoder">atcoder</a>
<a href="/ja/Range%20Add">Range Add</a>