累積和とその逆演算の一般化
※全然まとまってない
呼び方
自分はこの記事では、以下の呼び方を使います。特に、演算とそれを用いたアルゴリズムの違いに、"〜法"をとして区別します。
- 累積和を取る演算のことを"累積和", "cumsum" (cumulative sum)
- 累積和を取った後の一部の値を見て効率的に区間sumなどを得る方法のことを"累積和法" (別に累積和法という名称の別物があるようだが…)
- 累積和の逆演算である、各々の差分を取る演算のことを"diffs" (この"diffs"は自分が勝手につけた名前) ((数列の場合は)"階差数列"などとも言うらしい)
- diffsを取った後の状態で足してから最後に累積和を取って効率的に総和を得る方法のことを"累積和の逆法"
基本
累積和法は、ある"静的な"値がついている整数座標系において、初めにO(n)程度の前処理をすることによって、「ある規則的な(多項式で構成されていたり)の形の重み付きの総和」を効率的に(形によってはO(1))求めることができる方法です。
累積和の逆法は、値がつく整数座標系において、「ある規則的な(多項式で構成されていたり)の形」を効率的に(形によってはO(1))足し込み、O(n)程度で後処理をすることによってその値が得られる、という方法です。
分解と合成
"合成"とは単に各要素同士の和を取ることです。
ある状態をよりシンプルにするために、状態を「それらの総和が元の状態に等しい」複数の状態に"分解"をすることができます。
分解をした後に、それぞれに累積和法や累積和の逆法をして、最後に合成をすれば元に戻すことができます。
過去問題
早稲田大学プログラミングコンテスト I: その味は甘くて 解説スライド この問題では累積和の逆法を用いることができます。また、"分解と合成"を用いることができます。
Codeforces Round #161 (Div. 2) E. Rhombus Tutorial この問題では累積和法を用いることができます。また、"分解と合成"を用いることができます。
"座標系"と"向き"の一般化
一番シンプルなのは1次元や2次元グリッド上で、"右"や"下"にcumsumやdiffsをとることです。
様々な問題で「六角形の座標系」や「三角形の座標系」上で斜めの方向にやったりもします。
それらの"座標系"と(cumsumやdiffsを取る)"向き"を一般化できます。
各座標を値がついている頂点、"向き"による"近傍"を辺と考えられます。
例えば斜めの累積和では(A[y][x] = A[y-1][x-1] + value[y][x])としますが、これは各(y, x)から(y+1, x+1)に辺が伸びていて、その親を辿って総和を取っているようなふうに考えられます。
一般に、辺はDAGなら良いです。閉路があると無限大になってしまうからです。累積和はDAG上のDPとして考えられます。
一般に、(A[i] = Σ{j ∈ iの全ての親頂点: A[j]} + value[i])と書くことができます。
ここで注意したいのは、通常用いられる"向き"に対応する辺は入次数が1以下であることです。これによって値が(そのグラフの最大"幅"*各要素の最大値)より大きくなることがありません。
値と足し算の一般化
通常の問題では単純な整数値が用いられます。しかしこれを有理数に変えても問題無さそうだというのはなんとなくわかります。
さらに、MODを取る巡回群にしても問題無さそうだというのはなんとなくわかります。
一般に「可換群」(恒等元と逆元の存在, 結合法則と交換法則)であれば、累積和の逆法ができるための性質を満たすことがわかります。
作った問題「パスカルの三角形」の解法
別記事http://d.hatena.ne.jp/anta1/20130201/1359651597を参照。
この問題では値が巡回群で、さらに辺の入次数が1以下で無い、特殊な累積和の逆法を用いています。
同様の方法でフィボナッチ数列などの、DPで計算できるような値を足す累積和とその逆を用いた問題が作れる気がします。
cumsumとdiffsの基本性質
表記
Vを、各要素がある値を持っている頂点の集合とし、
辺Eに対して、(V #+ E)のようにして「Vに対してEでcumsumを取った結果」を表すことにします。
また、同様に(V #- E)をdiffsを取った結果を表すことにします。
V,Wの合成を(V >@< W)と表します。
diffsがcumsumの逆演算であるということ
(V #+ E #- E = V)と(V #- E #+ E = V)が常に成り立ちます。
辺の推移と順序
辺の推移(E,F)を{(v,w) | (v,u) ∈ E, (u,w) ∈ F}と定義します。このとき(推移(E, F) = 推移(F, E))であるとき、2つのcumsumやdiffsの順序が違っても結果は同じになります。
つまり、(E,F)が推移に対して"対称"なら(V #+ E #+ F = V #+ F #+ E), (V #- E #- F = V #- F #- E), (V #+ E #- F = V #- F #+ E)が全て成り立ちます。
3つ以上でも同様に成り立ちます。
合成での分配
( (V >@< W) #+ E = (V #+ E) >@< (W #+ E)), ( (V >@< W) #- E = (V #- E) >@< (W #- E))が成り立ちます。
累積和の逆法をする際に、「単純に足す」(V >@< W)と「diffsを取って簡単な形にして、それから足して、最後にcumsumを取る」(((V #- E) >@< (W #- E)) #+ E)が等しいことが、この分配法則と(V #- E #+ E = V)によって導けます。
coqで少し証明してみた
上記の法則をcoqで証明してみました。コードは超汚いです。
https://github.com/anta-/coq/blob/master/cumsum.v
DAG上の帰納法がめんどくさかったので、順序をトポロジカルソート済みとして手を抜いてます。このままでは、2つの違うトポロジカル順序上のエッジに対して連続して演算することができません。なので性質の証明もそのようになっています。恐らく性質に影響する問題無いとは思いますが…
コメント
上記の証明では、累積和の逆法に関してはなんとなく形式化できたのですが、累積和法関して形式化・証明をしていません。
累積和の逆法には「いもす法」というよく知られた名前がありますが、JOI等のクラスタ外の人間なので、意図的に使っていません。本人には少し失礼かもしれません。すいません。
