この間の opt (@opt_coder) さん作の yukicoder の問題

No.1172 Add Recursive Sequence - yukicoder

において，imos 法を漸化式で表される数列の加算に一般化することが問われました．この一般化はパッと見何をしているか分かりにくいのですが，線形代数のレンズを通して見ることですっきり理解できると感じたのでこの記事にまとめます．この記事を読めば，通常の imos 法で想定される「ある区間の値に全て 1 を足す」クエリを超えて，「ある区間に $1, 2, 4, 8, \ldots$ を足す」「ある区間にフィボナッチ数列を足す」などのクエリが処理できるようになるはずです．

復習: imos 法
線形代数を通して imos 法を理解する
- 操作の理解
- なぜ高速か？
一般化
応用例
まとめ

復習: imos 法

この記事では 1-indexed な記法を用います． imos 法は以下のような問題を解きたい時に用いる手法です．

長さで値が全て 0 の配列に対して，個の以下のクエリを適用する．
- クエリ $q$ : $l_q \leq i \lt r_q$ なる各整数 $i$ について， $a_i$ に 1 を加算する

愚直に加算していこうとすると， $\sum_{q=1}^Q ( r_q - l_q )$ 回程度の加算が必要になるため， $N$ や $Q$ が大きいときに計算量が非常に多くなってしまいます．

この問題を解決するため，imos 法では以下のような計算を行います．

クエリ $q$ について， $a_{l_q}$ を $+1$ し， $a_{r_q}$ を $-1$ する．
最後に， $i=1$ から $i=N-1$ の順に $a_{i+1} \leftarrow a_{i} + a_{i+1}$ という更新を行う．

こうすることで，正しい出力を $2Q + N$ 回程度の加算で計算することができます．典型 of 典型のようなテクニックなので使ったことがある人も多いと思います．

線形代数を通して imos 法を理解する

操作の理解

さて，この imos 法を線形代数の気持ちで理解していきます．そのために，配列を $N$ 次元縦ベクトルで表現することにします．そして，ベクトル $\boldsymbol{x}_q$ を $l_q \leq i \lt r_q$ なる各整数 $i$ について $x_{q, i} = 1$ ，それ以外の $i$ については $x_{q, i}=0$ なるベクトルとして定義します（以降，このベクトルのことをクエリベクトルと呼びます）．このとき，計算したいものは $\sum_{q=1}^Q \boldsymbol{x}_q$ になります．

さて，このような表記のもと，imos 法は実は以下のような操作をしていると理解することができます．

正則行列 $A$ に関して， $\boldsymbol{y} := \sum_{q=1}^Q A \boldsymbol{x}_q$ を計算する．ただし， $A$ は対角成分が $1$ ， $(i+1, i)$ 成分が $-1$ ，それ以外が $0$ であるような行列．例えば， $N=5$ のとき

$\begin{align} A = \begin{pmatrix} 1 & 0 & 0 & 0 & 0\\\ -1 & 1 & 0 & 0 & 0\\\ 0 & -1 & 1 & 0 & 0\\\ 0 & 0 & -1 & 1 & 0\\\ 0 & 0 & 0 & -1 & 1 \end{pmatrix} \\\ \end{align}$

である．

$A^{-1} \boldsymbol{y}$ を計算する．

ここで， $A^{-1} \boldsymbol{y} = A^{-1} (\sum_{q=1}^Q A \boldsymbol{x}_q) = \sum_{q=1}^Q A^{-1} A \boldsymbol{x}_q = \sum_{q=1}^Q \boldsymbol{x}_q$ より，この操作が正しい解を出力することが保証されます．

気持ちとしては， 行列 $A$ で表される線型写像によって一度全体を別の空間に飛ばし，そこでクエリを処理した上で $A^{-1}$ によってもとの空間に戻す という感じです．ここで 写像が線形であることは本質的です : なぜなら $A( \boldsymbol{x}+ \boldsymbol{y}) = A \boldsymbol{x} + A \boldsymbol{y}$ という線形性こそが飛ばした世界でクエリを処理することを正当化しているからです．また，写像が正則（逆行列が存在する）でないと情報が落ちてしまうのでもとの空間に戻せません．

具体例を見てみましょう． f:id:Theory_and_Me:20200823171222p:plain

黒の矢印が普通の計算手順を，赤の矢印が imos 法による計算手順を表します．

なぜ高速か？

これだけ見るとむしろ面倒で計算量が増えているだけに見えます．しかし，以下の 2 つの条件が満たされるため，この方法が非常に効率的になります．

(1) 全ての $q=1, \ldots, Q$ について， $A \boldsymbol{x}_q$ が スパース（非零要素数が少ない）である．

(2) $A^{-1} \boldsymbol{y}$ が 高速に 計算できる．

この計算法に必要な計算の回数は， $\mathrm{nnz}(\boldsymbol{x})$ をベクトル $\boldsymbol{x}$ の非零要素数， $I$ を $A^{-1} \boldsymbol{y}$ の計算に必要な計算回数として $\sum_{q=1}^Q \mathrm{nnz}(A \boldsymbol{x}_q) + I$ 程度となります．従って，(1) (2) の条件が満たされる場合には非常に高速な計算法になり得るわけです．

(1) が成り立つことは，飛んでくるクエリベクトル $\boldsymbol{x}_q$ において， $x_{q, i} - x_{q, i-1}$ は高々 2 つの $i$ を除いて 0 になることから確認できます．

f:id:Theory_and_Me:20200823171235p:plain

(2) が成り立つことを確認しましょう． $A^{-1} \boldsymbol{y}$ を計算することは， $A \boldsymbol{z} = \boldsymbol{y}$ なる連立方程式を $\boldsymbol{z}$ について解くことに他なりません．この連立方程式は，

$\begin{align} z_1 &= y_1, \\\ -z_1 + z_2 &= y_2, \\\ -z_2 + z_3 &= y_3, \\\ &\vdots \\\ -z_{N-1} + z_N &= y_N \\\ \end{align}$

となりますが，これを変形すると

$\begin{align} z_1 &= y_1, \\\ z_2 &= y_2 + z_1, \\\ z_3 &= y_3 + z_2, \\\ &\vdots \\\ z_N &= y_N + z_{N-1} \\\ \end{align}$

となります．この式に従って $z_1$ から順番に計算していくと， $z_i$ を計算する際には $z_{i-1}$ は計算済みであるため， $N$ 回程度の計算で $\boldsymbol{z}$ が求められることがわかります．また，このようにして $\boldsymbol{z}$ を求める手順は，通常の imos 法において最後に累積和を取っていく操作と同じであることも見てとれます．

一般化

さて，ここまでの議論を踏まえ，imos 法を一般化する方法を考えます．そのためには， なぜ imos 法がうまくいったのか を考えることが重要です．

なぜ $A \boldsymbol{x}_q$ がスパースになるのでしょう？　これは，飛んでくるクエリベクトル $\boldsymbol{x}_q$ において，端である $l_q, r_q$ 付近以外では $x_{q, i} = x_{q, i-1}$ という線形の関係式が成り立つ からです．この性質から，適当な行列 $A$ を取ってやることで $l_q, r_q$ 付近以外では $A \boldsymbol{x}_q$ を 0 にすることができるのです．
なぜ $A^{-1} \boldsymbol{y}$ が高速に計算できるのでしょう？　これに関しては， $A$ がスパースな下三角行列であることが重要です． $A^{-1} \boldsymbol{y}$ を計算することは，線形方程式 $A \boldsymbol{z} = \boldsymbol{y}$ を解くことに他なりません．このとき， $A$ が下三角行列であれば， $z_i$ に関する方程式に $z_1, z_2, \ldots, z_{i-1}$ および $y$ の要素しか出てきません．従って $z_1$ から順番に求めていくことで， $\mathrm{nnz}(A)$ 回程度の計算で $\boldsymbol{z}$ を計算することができるのです． $A$ がスパースであれば $\mathrm{nnz}(A)$ は非常に小さくなり，高速な計算が実現できます．一般の $n \times n$ の係数行列を持つ線形方程式を普通に解こうとすると $\Theta (n^3)$ 回程度の計算が必要であることから，これが非常に良い性質であることが見てとれます．
$A$ が下三角行列であることは， $A$ の正則性の観点からも重要です．下三角行列に関する重要な事実として，行列式の値が対角成分の積に等しいというものがあります． $A$ が正則 $\Leftrightarrow$ $A$ の行列式の値が非零であることから， $A$ は 対角成分が全て非零でありさえすれば正則 であることが保証されます．

逆に言えば，上記の性質が成り立つことを目指せば，別の問題においても類似の効率的な手法を設計することが可能です．これを見ていきましょう．

応用例

等比数列

次のような問題を考えてみましょう．

長さで値が全て 0 の配列に対して，個の以下のクエリを適用する．
- クエリ $q$ : $l_q \leq i \lt r_q$ なる各整数 $i$ について， $a_i$ に $2^{i-l_q}$ を加算する

$1, 2, 4, 8, \ldots$ というような数列を区間に足していくイメージです．ここでは簡単のため公比 2 の等比数列を考えていますが，他の公比の場合も同様の議論が可能です．

この問題を imos 法と同様にして処理することを考えましょう．重要な性質は，各クエリベクトルにおいて 端である $l_q, r_q$ 付近以外では $x_{q, i} = 2 x_{q, i-1}$ という線形の関係式が成り立つ ことです．このことを考慮すれば， $A \boldsymbol{x}_q$ をスパースにするためには， $A$ として対角成分が $1$ ， $(i+1, i)$ 成分が $-2$ ，それ以外が $0$ であるようなものを取れば良さそうです．例えば $N=5$ のときは

$\begin{align} A = \begin{pmatrix} 1 & 0 & 0 & 0 & 0\\\ -2 & 1 & 0 & 0 & 0\\\ 0 & -2 & 1 & 0 & 0\\\ 0 & 0 & -2 & 1 & 0\\\ 0 & 0 & 0 & -2 & 1 \end{pmatrix} \\\ \end{align}$

です．この行列はスパースな下三角行列であり，さらに対角成分が全て非零であることから，必要な性質を全て備えています．

$A^{-1} \boldsymbol{y}$ の計算，すなわち $A \boldsymbol{z} = \boldsymbol{y}$ なる $\boldsymbol{z}$ を求める操作は，

$\begin{align} z_1 &= y_1, \\\ - 2 z_1 + z_2 &= y_2, \\\ - 2 z_2 + z_3 &= y_3, \\\ &\vdots \\\ \\ -2 z_{N-1} + z_N &= y_N \\\ \end{align}$

より

$\begin{align} z_1 &= y_1, \\\ z_2 &= y_2 + 2 z_1, \\\ z_3 &= y_3 + 2 z_2, \\\ &\vdots \\\ z_N &= y_N + 2 z_{N-1} \\\ \end{align}$

となります．毎回値を 2 倍しながら累積和を取るイメージですね．

具体例で見てみましょう． f:id:Theory_and_Me:20200823171245p:plain

うまくクエリベクトルをスパースにしつつ正しい解を出力できていることが分かると思います．

フィボナッチ数列

更なる応用として，区間へのフィボナッチ数列の加算を考えてみましょう．

長さで値が全て 0 の配列に対して，個の以下のクエリを適用する．
- クエリ $q$ : $l_q \leq i \lt r_q$ なる各整数 $i$ について， $a_i$ に $F_{i-l_q}$ を加算する．ただし， $F_i$ は $i$ 番目のフィボナッチ数．

この問題を imos 法と同様にして処理することを考えましょう．重要な性質は，各クエリベクトルにおいて 端である $l_q, r_q$ 付近以外では，フィボナッチ数列の定義より $x_{q, i} = x_{q, i-1} + x_{q, i-2}$ という線形の関係式が成り立つ ことです．このことを考慮すれば， $A \boldsymbol{x}_q$ をスパースにするためには， $A$ として対角成分が $1$ ， $(i+1, i)$ 成分及び $(i+2, i)$ 成分が $-1$ ，それ以外が $0$ であるようなものを取れば良さそうです．例えば $N=5$ のときは

$\begin{align} A = \begin{pmatrix} 1 & 0 & 0 & 0 & 0\\\ -1 & 1 & 0 & 0 & 0\\\ -1 & -1 & 1 & 0 & 0\\\ 0 & -1 & -1 & 1 & 0\\\ 0 & 0 & -1 & -1 & 1 \end{pmatrix}\\\ \end{align}$

です．この行列はスパースな下三角行列であり，さらに対角成分が全て非零であることから，必要な性質を全て備えています．

$A^{-1} \boldsymbol{y}$ の計算，すなわち $A \boldsymbol{z} = \boldsymbol{y}$ なる $\boldsymbol{z}$ を求める操作は，

$\begin{align} z_1 &= y_1, \\\ - z_1 + z_2 &= y_2, \\\ - z_1 - z_2 + z_3 &= y_3, \\\ - z_2 - z_3 + z_4 &= y_4, \\\ &\vdots \\\ -z_{N-2} -z_{N-1} + z_N &= y_N \\\ \end{align}$

より

$\begin{align} z_1 &= y_1, \\\ z_2 &= y_2 + z_1, \\\ z_3 &= y_3 + z_1 + z_2, \\\ z_4 &= y_4 + z_2 + z_3, \\\ &\vdots \\\ z_N &= y_N + z_{N-2} + z_{N-1} \\\ \end{align}$

となります．累積和とは違う形になっていることが分かると思います．

具体例を見てみましょう． f:id:Theory_and_Me:20200823171257p:plain

線形漸化式で定義される数列

フィボナッチ数列以外でも，なんらかの線形漸化式で定義される数列にもここでの議論が応用できます．まさに冒頭で挙げた問題である Add Recursive Sequence はこれを問うている問題であり，同様の考え方で解くことができます．

注意点としては，線形漸化式の項数が多くなればなるほど，計算量が増えていくということです． $K$ 項間漸化式であれば， $A$ をかけた後のクエリベクトルの非零要素の数は最大 $2(K-1)$ 個となるため，一度の加算に必要な計算量は最大 $2(K-1)$ 回程度となります．また，最後に $A^{-1}$ を掛ける操作にも $KN$ 回程度の計算が必要になります．