内容別リスト/高速化系/sliding window法 - 競技プログラミング用 知識集積所

---

雑な説明

要素数nのデータのうち連続するm個のデータの何か（和、積、xor、最大値、など）の中で、条件を満たすものがあるか、または最大値や最小値を求める。
通常の方法でやれば計算回数がO(mn)になるところ、O(m+n)で済む。

レベル

ABCのC問題以降。

アルゴリズム内容

例えば10個のうちの連続する5個の和の最大値を探す場合、以下のようにする。

データ											計算方法	暫定最大値
3	1	4	1	5	9	2	6	5	3		3+1+4+1+5=14	14
3	1	4	1	5	9	2	6	5	3		14-3+9=20	20
3	1	4	1	5	9	2	6	5	3		20-1+2=21	21
3	1	4	1	5	9	2	6	5	3		21-4+6=23	23
3	1	4	1	5	9	2	6	5	3		23-1+5=27	27
3	1	4	1	5	9	2	6	5	3		27-5+3=25	27

通常であれば各和の計算に4回の足し算が必要であるが、この方法では最初以外和1回と差1回で済む。
計算回数が2回で済むことは連続何個のデータを処理する場合でも変わらない。
そのため、連続10万個の和などが必要な場合にはこのアルゴリズムを使うことで大幅に高速化される。

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

演算	追加	削除	補足
総和	+	-
総乗	*	/
xor	^	^
最小値	.emplace()	.erase()	multisetで管理して、*(s.begin())で取得する。 重複値を消すためにイテレータで消す必要があるので注意。
最大値	.emplace()	.erase()	multisetで管理して、*(s.rbegin())で取得する。 重複値を消すためにイテレータで消す必要があるので注意。
種類数	++	-- .erase()	mapで内容->個数を管理、0個になったらキー自体を消す。 mapのsize()で種類数を取得できる。

注意点

可変長にはできない。

実装のわかりやすさがメリットであり、柔軟な対応力はあまりない。
長さを可変にしたい場合は他の類似アルゴリズムを用いること。

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

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

関連アルゴリズム

尺取法

範囲の左右を両方動かして、条件を満たす範囲を探す目的である点が類似。
こちらのメリットは実装が簡単であること、あちらのメリットは可変長であること。

累積和

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

Fenwick木（未作成）

累積和の上位互換。

segment木（未作成）

Fenwick木の上位互換。