尺取法

概要

要素数 $n$ のデータのうち、連続する何個かのデータについて和、積、種類数などを調べるアルゴリズム。
条件を満たす区間がいくつあるか数えたり、条件を満たす最長区間や最短区間を求めたりする。

通常は全ての区間を調べると $O(n^2)$ かかる。
区間に要素を追加する処理と削除する処理が $O(1)$ なら、尺取法を使うことで $O(n)$ で済む。

アルゴリズム内容

例えば、以下の数列について、和が $10$ 以下になる連続部分列の個数を求める場合を考える。

3 1 4 1 5 9 2

左端を left、右端の $1$ つ外側を right とする。
現在の区間を [left,right) として管理する。

右端を進めて区間を広げ、和が $10$ を超えた場合だけ左端を進めて区間を狭める。
和が $10$ 以下になった時点で、右端が同じで条件を満たす区間は right-left 個ある。

処理は以下のように進む。
黄色の部分が現在の区間 [left,right) である。
赤色の部分は、その行で更新された区間数総計である。

右端がこれ以上進めないので終了し、答えは $15$ 個となる。

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

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

範囲を広げたときに値が減らないような演算であれば何でも使える。
また、条件を満たす区間の個数以外にも、条件を満たす最長区間なども求められる。

実装方法は大きく $3$ つある。
以下はいずれも上の例に対応する。
また、「範囲が空の場合は形式的には条件を満たす」という前提で書いている。
今回は、形式的には和が $0$ であり、$10$ 以下という条件を満たしている。

二重ループで書く方法

int limit = 10;
int sum = 0;
long long interval_num = 0;

for (int left=0, right=0; right<n; ) {
  sum += a[right];
  right++;
  while (sum>limit) {
    sum -= a[left];
    left++;
  }
  interval_num += right-left;
}

右側カウンタは開区間として扱っている。
つまり、現在の区間は left<=i&&i<right となる。

二重ループなので一見 $O(n^2)$ に見えるが、left と right はどちらも高々 $n$ 回しか進まない。
したがって、区間への追加・削除が $O(1)$ なら全体で $O(n)$ である。

whileループの中でif文を使う方法

int limit = 10;
int sum = 0;
long long interval_num = 0;

int left = 0;
int right = 0;
while (true) {
  if (sum>limit) {
    sum -= a[left];
    left++;
  } else {
    interval_num += right-left;
    if (right==n) break;
    sum += a[right];
    right++;
  }
}

こちらも右側カウンタは開区間として扱っている。

queueを使ってforループで書く方法

int limit = 10;
int sum = 0;
long long interval_num = 0;

queue<int> que;
for (int i : a) {
  que.emplace(i);
  sum += i;
  while (sum>limit) {
    sum -= que.front();
    que.pop();
  }
  interval_num += que.size();
}

こちらは右端を閉区間として考える形になる。
ただし、コード中に右側カウンタ自体は登場しない。

注意点

右側主導で書いた方が楽。

尺取法は、左端を $1$ つずつ進めながら、右端をwhileループで伸ばす形でも書ける。
しかし、その場合は右端が範囲外へ進まないようにする条件がややこしくなりやすい。
右端を主導して進める形の方が、単純なコードで書きやすい。

関連知識

ツーポインタ法

$2$ つの位置を単調に動かしながら調べる点が共通する。
尺取法では、主に連続区間の左右の端を動かして、条件を満たす区間を管理する。

sliding window法

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

累積和

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

累積和と二分探索を組み合わせると、尺取法とほぼ同じことができる場合が多い。
しかし、種類数のように範囲の削減が単純な処理で済まないものは、累積和では対応できない。
また、計算量は $O(n\log n)$ となり、尺取法の $O(n)$ よりわずかに遅い。

Fenwick木

累積和の上位互換。

segment木

Fenwick木の上位互換。