目次

スライド最小値、SWAG

大まかな問題設定

以下、区間内の要素全ての $\oplus$ の結果を、足し算に限らなくとも単に「総和」と表現する。

使えうるアルゴリズム例

クエリの性質により、いくつかの解法がある。(性質や計算量に関しては抜けがあるかも)

区間のマージ $(A_i \oplus ... \oplus A_{j-1}) \oplus (A_{j} \oplus ... \oplus A_{k-1})$ 演算1回の計算量を $O(\alpha)$ とする。
区間に要素を1つ加える $(A_i \oplus ... \oplus A_{j-1}) \oplus A_{j}$ (または取り除く)演算1回の計算量を $O(\beta)$ とする。

アルゴリズム 元と演算が満たすべき性質 クエリの性質 事前計算量 $Q$ クエリ通しての計算量
累積和 逆演算の存在 $O(\alpha N)$ $O(Q\alpha)$
セグメント木 モノイド(結合法則+単位元の存在) $O(\alpha N\log{N})$ $O(Q\alpha\log{N})$
SparseTable 結合法則+冪等性 $O(\alpha N\log{N})$ $O(Q\alpha)$
Mo's Algorithm 特になし? オフライン $O(Q \log{Q})$ $O(N\sqrt{Q}\beta)$
スライド最小値 演算が最小値or最大値 両端が単調増加 なし $O(N\beta)$
SWAG 結合法則 両端が単調増加 なし $O(N\beta + Q\alpha)$

累積和は、足し算に対する引き算、かけ算に対する割り算など、逆演算が可能な場合に使える。
$f(l,r)$ を「$l~r-1$ の総和」として、$f(1,R_i)-f(1,L_i)=f(L_i,R_i)$ となることを利用する。

セグメント木は、クエリ計算量が他より劣るが、 この中では唯一、途中で任意の $A_i$ の更新があっても大丈夫なので汎用性が高い。

SparseTableは、冪等性($A \oplus A = A$)という性質を満たす必要はあるが、 逆演算がなく累積和が使えないmin,gcdなどに対して使える。

以降のクエリあたり計算量に $\beta$ が付くものは、 現在求まっている区間の「左端を1つ縮める」「右端を1つ伸ばす」などをすることで 尺取法のように区間をずらしていくアルゴリズムである。

Mo's Algorithm は、全クエリを最初にソートして分類するためオフラインである必要があるが、 特に区間同士のマージ $\alpha$ より、区間に要素を1加える処理 $\beta$ の方が高速な時に使える。

スライド最小値やSWAGは、 クエリの両端が単調増加($L_i \le L_{i+1}$ かつ $R_i \le R_{i+1}$、$(i=1,2,...,N-1)$)を満たす場合、 事前計算不要で高速に求められる。

以下では、このスライド最小値とSWAGについてまとめている。

スライド最小値

      i:  0  1  2  3  4  5  6
      A:  3  1  4  2  8  5  7

クエリ1: |----|
クエリ2: |----------|
クエリ3:    |----------|
クエリ4:          |----|
クエリ5:                   |-|

これは、両端キュー(Deque)で実現できる。($Q$ とする)

$Q$ には、直感的に言えば、「現在の区間における、単調増加部分列のindex」を持っておく。

例
i:  0  1  2  3  4  5  6
A:  3  1  4  2  8  5  7

現在の                スライド
 L  R     A[L:R]      最小値のQ   最小値
 -----------------------------------------
 0  0     []           []         -
 0  1     [3]          [0]        A[0] = 3
 0  2     [3 1]        [1]        A[1] = 1
 0  3     [3 1 4]      [1 2]      A[1] = 1
 0  4     [3 1 4 2]    [1 3]      A[1] = 1
 1  4     [1 4 2]      [1 3]      A[1] = 1
 2  4     [4 2]        [3]        A[3] = 2
 2  5     [4 2 8]      [3 4]      A[3] = 2
 2  6     [4 2 8 5]    [3 5]      A[3] = 2
 2  7     [4 2 8 5 7]  [3 5 6]    A[3] = 2
 3  7     [2 8 5 7]    [3 5 6]    A[3] = 2
 4  7     [8 5 7]      [5 6]      A[5] = 5

Rを1増やす操作がappend、Lを1増やす操作がpopleftに相当する。

SWAG (Foldable Queue)

Sliding Window Aggregationの頭文字。

「SWAG」がアルゴリズムの名前、それを実現するデータ構造が「Foldable Queue」と呼ばれている?

概念的には上記scrapboxの図がわかりやすい。

本来のqueueを途中で割って、2つのstack(cum_fwd, cum_bwd)に分けて累積和を管理する。
また、後半部分に関しては生値(raw_bwd)も持っておく。

以下のように累積和を持つことで、cum_fwd[末尾] + cum_bwd[末尾] で現在の総和が得られる。

                                 raw_bwd
生値                             [ a3  a4     a5       ]

        cum_fwd                  cum_bwd
累積和  [ a0+a1+a2  a1+a2  a2 ]  [ a3  a3+a4  a3+a4+a5 ]    ※フォント幅の都合上、⊕ を + で代用
        末尾←-------------先頭  先頭-------------→末尾

append は普通に cum_bwd に追加すればよい。popleft も cum_fwd が存在する間は普通に pop すればよい。

cum_fwdに何も無い状態でさらに popleft が呼ばれたときは…

                                 raw_bwd
生値                             [ a3  a4     a5       ]

        cum_fwd                  cum_bwd
累積和  [                     ]  [ a3  a3+a4  a3+a4+a5 ]
        末尾←-------------先頭  先頭-------------→末尾

↓↓↓

bwdを全てfwdに移し替える。
この時、累積和の取る方向が異なり再計算するので、bwdに関しては生値(raw_bwd)も必要となる。
(一方、raw_fwd は無くてもよい)

                                 raw_bwd
生値                             [                     ]

        cum_fwd                  cum_bwd
累積和  [ a3+a4+a5  a4+a5  a5 ]  [                     ]
        末尾←-------------先頭  先頭-------------→末尾

交換法則が成り立たない場合は、移し替えるときの演算の順序に注意。(左からかけていく)

popleft の計算量は、移し替えが発生するタイミングで大きくなるが、1要素につき1回しか移動は発生しないので、均すと $O(1)$ となる。

append は $O(\beta)$、fold はマージが1回発生するので $O(\alpha)$ となる。

Python3

Foldable Deque

SWAGは、Deque(popleft, append に加え、appendleft, pop にも対応した版)に拡張できる。

後ろから前へ移し替えるとき(あるいはDequeの場合は前から後ろへの移動も発生するが)、全て移し替えるのではなく、半分は残す。
(残すといっても、累積和の起点が変わるので、前も後ろもいずれにしろ全て再計算は必要になる)

クエリによっては、後ろ→前→後ろ→前→… と移動が多く発生し、計算量的に大丈夫?となるが、、、

ある移動で半分に分かれた内の片方が全て無くならないと、もう片方の再移動は発生しない。
よって、生き残る要素数は移動のたびに最悪でも半分以下になっていき、全要素を均すと1要素あたりの移動は平均 $O(1)$ 回しか発生しないので大丈夫。