https://imoz.jp/algorithms/imos_method.html

1. 考え方

• ほしい値の差分を考えて後で累積和をする。
• 差分がスパースになって非ゼロ成分が O(1) 個しかない場合は O(1) の計算量で処理できて嬉しい。
• 線形性が使えるので複数個の重ね合わせができる。

2. 1変数和分差分

数列といえば写像 $\mathbb{N}\to \mathbb{R}$ を表すことにする。

自然数は 0 から始まる。

2.1. 和分

数列 $a$ に対して、$\Sigma a$ を以下で定義する

• $\Sigma a (x) = \sum_{i=0}^x a(i)$

線形性が成り立つ。

$\Sigma$ は $\mathbb{R}^\mathbb{N} \to \mathbb{R}^\mathbb{N}$ の線形変換だと思える。（以下の $\Delta$ なども同様）

2.2. 差分

数列 $a$ に対して、$\Delta a$ を以下で定義する

• $\Delta a (0) = a(0)$
• $\Delta a(x) = a(x) - a(x-1) \quad (x \geq 1)$