スライド最小値、SWAG

大まかな問題設定

長さ $N$ の数列 $A=(A_1,...,A_N)$ と、二項演算 $\oplus$ がある（足し算、最小値、など）
$A$ に対するいくつかの区間クエリがある
$i$ 番目のクエリでは、 $[L_i,R_i)$ が与えられ、 $A_{Li} \oplus A_{Li+1} \oplus ... \oplus A_{Ri-1}$ を求める
全ての区間クエリに対し、高速に答えたい

以下、区間内の要素全ての $\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$ の方が高速な時に使える。

Mo's algorithm - ei1333の日記

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

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

スライド最小値

要件
- 演算は最小値（最大値）限定
- 全クエリに渡って $L_i \le L_{i+1}$ かつ $R_i \le R_{i+1}$ （クエリの両端が単調増加）

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

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

できること
- 今の区間を $[L,R)$ として、
  - append: 区間の右端に $R$ を追加
  - popleft: 区間の左から $L$ を削除
  - fold: 現在の区間の最小値（最大値）を求める

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

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

append(R)
- $Q$ の末尾から見ていって、 $A[Q[-1]] \lt A[R]$ となるまで $Q$ からpopする
- $Q$ の末尾に $R$ を追加する（※値ではなく、index）
popleft(L)
- もし、 $Q[0]==L$ なら、 $Q$ の先頭を削除する
fold()
- $A[Q[0]]$ が最小値

例
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の頭文字。

Sliding Window Aggregation - data-structures

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

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

できること
- append(x): queueの末尾に $x$ を追加する
- popleft(): queueの先頭要素を削除する
- fold(): queueの全要素の総和を得る

本来の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 にも対応した版）に拡張できる。

Foldable-Queue(SWAG) およびそのDeque版について - Qiita

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

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

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