【競プロ】いもす法

いもす法は、配列に対して特定の区間を増減した結果を高速で求めるアルゴリズム

雰囲気

配列のある区間に値$\alpha$を足し、別の区間に$\beta$を足し、…としたいときに、

1. 区間の初めに$+\alpha$、区間の終わりに$-\alpha$しておく
   区間の初めに$+\beta$、区間の終わりに$-\beta$しておく
   ...
2. あとで累積和を求める

とすることで、毎回区間に値を足すよりも高速に配列の値を求められる

例

例えば、長さ6の配列arrが以下のように与えられたとする

[0 0 0 0 0 0]

区間[1, 3]に＋2を行い、その後区間[2, 5]に＋3を行うとする

---

いもす法を用いて解く
最初に区間[1, 3]に＋2を行うため、arr[1]を+2してarr[4]を-2する

[0 2 0 0 -2 0]

次に区間[2, 5]に+3を行うため、arr[2]を+3する（arr[6]は範囲外なので-3しなくていい）

[0 2 3 0 -2 0]

最後に累積和（arrを左から累積した値）を求める

[0 2 5 5 3 3]

ちゃんと区間[1, 3], [2, 5]の共通部分[2, 3]が2+3=5になっている！

アルゴリズム

クエリが$Q$回あり、各$t\in [Q]$に対し区間$[i_t,j_t)$を$+\alpha_t$する場合

1. 各$t\in [Q]$に対し、$A_{i_t}$を$+\alpha_t$、$A_{j_t}$を$-\alpha_t$する
2. 配列$A$の累積和$S$を求める
   • $S_0=A_0, S_i=S_{i-1}+A_i$

1. は$O(Q)$で行うことができ、2. は$O(N)$で行うことができるので高速

記法について

$[Q]=\{1,2,\dots,Q\}$

高次元版

簡単のため、2次元とする
クエリが$Q$回あり、各$t\in [Q]$に対し区間$[i_t,j_t)\times [k_t,l_t)$を$+\alpha_t$する場合

1. 各$t\in [Q]$に対し、$A_{i_t,k_l}, A_{j_t,l_l}$を$+\alpha_t$、$A_{i_t,l_l}, A_{j_t,k_l}$を$-\alpha_t$する
2. 配列$A$の累積和$S$を求める
   • $S_{0,0}=A_{0,0}, S_{i,j}=\sum_{x\le i, y\le j} A_{x,y}$

なぜこうなるのか

区間の増減に対して差分をとっていることに対応する
あとで累積和をとることで実際の値になる

証明

長さ$N$の数列

$$S=\{S_i\}_{i\in [N]}$$

および$Q$個の数列

$$\alpha^{(t)}=\{a^{(t)}_i\}_{i\in [N]} \quad (t\in [Q])$$

を考える
ここで、$S=\sum_{t\in [Q]}a^{(t)}$、つまり

$$S_i=\sum_{t\in [Q]}a^{(t)}_i \quad \cdots (1)$$

とすると差分を取って、$\Delta S=\sum_{t\in [Q]}\Delta a^{(t)}$となる

差分について

ここで、数列$x=\{x_i\}_{i\in [N]}$に対して差分$\Delta x=\{\Delta x_i\}_{i\in [N]}$を

$$\Delta x_i=x_i-x_{i-1}$$

とする（ただし、$x_0=0$とする）
(1)に対して差分を取ると、

$$\begin{align*} \Delta S_i &=\Delta ( \sum_{t\in [Q]}a^{(t)}_i ) \\ &=\sum_{t\in [Q]}a^{(t)}_i - \sum_{t\in [Q]}a^{(t)}_{i-1} \\ &=\sum_{t\in [Q]}(a^{(t)}_i - a^{(t)}_{i-1}) \\ &=\sum_{t\in [Q]} \Delta a^{(t)}_i \end{align*}$$

ここで、$x_i=\sum_{j\le i}\Delta x_j$となることから、

$$\begin{align*} S_i &=\sum_{j\le i}\Delta S_j \\ &=\sum_{j\le i}\sum_{t\in [Q]} \Delta a^{(t)}_j \end{align*}$$

特に、数列$a=\{a_i\}_{i\in [N]}$を区間$[i_t,j_t)$で$\alpha^{(t)}$、その他で$0$の数列だとすると、

$$\Delta a_i =\begin{cases} \alpha^{(t)} &\text{if } i=i_t \\ 0 &\text{otherwise} \\ -\alpha^{(t)} &\text{if } i=j_t \end{cases}$$

これは、1. でもとめた配列に$\sum_{t\in [Q]} \Delta a_i$が対応し、その累積和 2. に$\sum_{j\le i}\sum_{t\in [Q]} \Delta a^{(t)}_j$が対応していることから、アルゴリズムの正当性が言える

（本来の証明と異なると思います）

参考

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