スライド最小値、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)$ とする。

累積和は、足し算に対する引き算、かけ算に対する割り算など、逆演算が可能な場合に使える。
$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に相当する。

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

from typing import TypeVar, Generic, Callable, List

T = TypeVar('T')


class FoldableQueue(Generic[T]):
    def __init__(self, func: Callable[[T, T], T], factory: Callable[[], T]):
        self.raw_b: List[T] = []  # 後ろの生値
        self.cum_f: List[T] = [factory()]  # 前の累積値
        self.cum_b: List[T] = [factory()]  # 後ろの累積値
        self.func = func

    def append(self, x: T):
        self.raw_b.append(x)
        self.cum_b.append(self.func(self.cum_b[-1], x))

    def move(self):
        assert len(self.cum_f) == 1
        while len(self.cum_b) > 1:
            self.cum_f.append(self.func(self.raw_b.pop(), self.cum_f[-1]))
            self.cum_b.pop()

    def popleft(self):
        if len(self.cum_f) == 1:
            self.move()

        assert len(self.cum_f) > 1

        return self.cum_f.pop()

    def fold(self):
        return self.func(self.cum_f[-1], self.cum_b[-1])

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

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

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

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

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