sliding window法

概要

要素数 $n$ のデータのうち連続する $m$ 個のデータについて、和、積、xor、最大値などを調べる方法。
条件を満たす区間があるか調べたり、それぞれの区間で得られる値の最大値や最小値を求めたりする。

毎回 $m$ 個全てを計算し直すと $O(mn)$ かかる。
区間への追加や削除の処理が $O(1)$ なら、sliding window法を使うことで $O(m+n)$ で済む。

アルゴリズム内容

例えば、以下の $10$ 個のデータから、連続する $5$ 個の和の最大値を探す場合を考える。

3 1 4 1 5 9 2 6 5 3

最初の $5$ 個の和は $3+1+4+1+5=14$ である。
次の区間へ移るときは、区間から外れる $3$ を引き、新しく入る $9$ を足せばよい。
そのため、$14-3+9=20$ と求められる。

同様に繰り返すと、以下のようになる。
黄色の部分が現在見ている区間である。

通常であれば、各区間について $5$ 個の和を最初から計算する必要がある。
しかし、この方法なら $5$ 個の和を素直に計算するのは最初だけ。
$2$ 番目以降は、区間から外れる値を引き、新しく入る値を足すだけで次の区間の和が求められる。
連続するデータの個数 $m$ が大きくても、区間を $1$ つずらす処理量は変わらない。

総和以外にも適用できる演算がある。

種類数は map の ssize(m) または m.size() で取得できる。

multiset から重複する値を $1$ 個だけ消す場合は、値ではなくイテレータを指定して .erase() すること。
なお、最大値最小値に関しては deque を用いる別アルゴリズムの方が簡単かもしれない。

追加・削除自体に $O(1)$ より時間がかかる場合は、全体の計算量もその分増える。

注意点

可変長にはできない。

実装のわかりやすさがメリットであり、柔軟な対応力はあまりない。
区間の長さを可変にしたい場合は、尺取法などを用いる。

ループの終了条件に注意。

$10$ 個のデータのうち連続する $5$ 個を処理する場合、対象となる区間は $6$ 個ある。
$n$ 個のデータの連続する $m$ 個を処理する場合、最後の区間は $n-m$ 番目から始まる。
最後の区間を処理し忘れないこと。

関連知識

ツーポインタ法

$2$ つの位置を動かしながらデータを調べる点が共通する。
sliding window法では、固定長の区間の左右を同時に進めていく。

尺取法

範囲の左右を両方動かしながら区間を調べる点が類似する。
sliding window法は区間長が固定なので実装が簡単で、尺取法は区間長を可変にできる。

累積和

一定区間の演算結果を求める点が類似する。
sliding window法のメリットは対応する演算の種類が多いこと。
累積和のメリットは後から好きな区間の情報を好きなだけ取れること。

Fenwick木

累積和の上位互換。

segment木

Fenwick木の上位互換。

差分更新

sliding window法は、範囲の変更を差分更新として扱うことで高速化している。