{ }codelper

学ぶ › TypeScript

アルゴリズム · 29

累積和と尺取り法

区間の和を引き算1回で求め、二つの位置を前にだけ動かして区間を探します。

累積和は、前から足してきた値を表に書いておくことです。
尺取り法は、リストの上の二つの位置を動かしながら答えを探す方法です。
下の例は、6個の数について「l番目から r番目までの和」という質問3つに答え、和が 16 以上になるいちばん短い連続した区間の長さを求めます。

import { readFileSync } from "node:fs";const t: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q, s] = t;const a: number[] = t.slice(3, 3 + n); // prefix[i] = 앞에서 i개의 합 (prefix[0] = 0)const prefix: number[] = new Array(n + 1).fill(0);for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + a[i]; for (let k = 0; k < q; k++) {  const l = t[3 + n + 2 * k], r = t[4 + n + 2 * k];  console.log(prefix[r] - prefix[l - 1]); // l번째부터 r번째까지의 합} // 합이 s 이상인 가장 짧은 이어진 구간: left와 right는 앞으로만 간다let best = 0, left = 0, window = 0;for (let right = 0; right < n; right++) {  window += a[right];  while (window >= s) {    if (best === 0 || right - left + 1 < best) best = right - left + 1;    window -= a[left];    left++;  }}console.log(best);
stdin
6 3 16
5 1 9 2 7 4
1 6
2 4
3 3
stdout
28
12
9
3

ポイント

  • 質問のたびに最初から足し直すと、同じ足し算を繰り返すことになります。
    そこで prefix[i] に「前から i個の和」をあらかじめ書いておきます。
    数が 5 1 9 2 7 4 なら、表は 0 5 6 15 17 24 28 です。
  • l番目から r番目までの和は prefix[r] - prefix[l - 1] です。
    前から r個の和から前の l − 1個を取り除くと、そのあいだだけが残ります。
    表は1回だけ作り、質問ごとに引き算1回で済みます。
  • 表を1マス長く（n + 1マス）作って prefix[0] = 0 にしておくと、l が 1 のときも同じ式がそのまま使えます。
  • 尺取り法は、区間の左端 left と右端 right を持ちます。
    right を1つ進めて数を入れ、和が s 以上のあいだは長さを記録して left を1つ進め、数を抜きます。
  • どちらの位置も後ろに戻らないので、それぞれ多くても n回しか動きません。
    すべての区間を一つずつ試さなくてよいのは、数がすべて正なので、区間を伸ばすと和が増え、縮めると減るからです。
  • 値が10億くらいになると、3個足しただけで32ビット整数（約21億まで）を超えます。
    和を入れる変数と表は64ビットにします。

言語ごとの書き方

Pythonprefix = [0] * (n + 1) を作って prefix[i + 1] = prefix[i] + a[i]。
list(itertools.accumulate(a, initial=0)) でも同じ表ができます。
整数に大きさの制限はありません
JavaScriptnew Array(n + 1).fill(0)。
数は 2^53（約9000兆）まで正確なので、10億くらいの値が数万個あっても和はそのまま入ります
TypeScriptJavaScript と同じです。
表の型は number[]
Javalong[] prefix = new long[n + 1]; — 新しい配列は 0 で埋まっています。
和を入れる変数も long
C#long[] prefix = new long[n + 1]; — 新しい配列は 0 で埋まっています。
和を入れる変数も long
C++std::vector<long long> prefix(n + 1, 0);。
和を入れる変数も long long
Clong long prefix[10001]; を関数の外に置くと 0 で埋まっています。
表示は %lld
Craykonprefix = 新リスト(n + 1, 0);。
数は 2^53 まで正確です。
区間を縮める繰り返しは 間 (window >= s) { }

よくある間違い

prefix[r] - prefix[l] で引いた

a = [5, 1, 9, 2, 7, 4]
prefix = [0, 5, 6, 15, 17, 24, 28]
l, r = 2, 4
print(prefix[r] - prefix[l])

→ 11 — 2番目の数 1 まで引いてしまいました。正しい答えは 12 です

引くのは prefix[l - 1] です。
l番目の数は残したいので、その前の l − 1個だけを取り除きます。

区間を縮めるのに while ではなく if を使った

const a = [1, 1, 1, 10], s = 10;
let best = 0, left = 0, window = 0;
for (let right = 0; right < a.length; right++) {
  window += a[right];
  if (window >= s) {
    if (best === 0 || right - left + 1 < best) best = right - left + 1;
    window -= a[left];
    left++;
  }
}
console.log(best);

→ 4 — 正しい答えは、10 だけの区間の 1 です。1周に1つしか縮めないので、left が追いつきませんでした

和が s 以上のあいだ縮め続ける必要があるので、while で書きます。

累積和を int に入れたJava · C# · C++ · C

int[] a = {1000000000, 1000000000, 1000000000};
int[] prefix = new int[4];
for (int i = 0; i < 3; i++) prefix[i + 1] = prefix[i] + a[i];
System.out.println(prefix[3]);

→ -1294967296 — 30億が int（約21億まで）に入らず、あふれました

表と和の変数を long（C・C++ は long long）にします。
値一つ一つは int に入っても、和はあふれることがあります。

言語ごとの違い
累積和は、値が変わらないリストに対して和を何度も聞かれるときに使います。
尺取り法で和を見るこの方法は、数がすべて正のときだけ正しく動きます。
負の数が混ざると区間を伸ばしても和が減ることがあり、-1 5 で和が 5 以上の区間を探すと、5 一つの区間を見逃して 0 を出します。
番号を 0 から数えるのか 1 から数えるのかを先に決め、小さな例を手でたどってみましょう。

練習問題

  1. 二つの入口の入場記録をまとめる8P0260
  2. 区間の和をすばやく8P0039
  3. 整列された数で和が S になる二つ8P0069
  4. バスがいちばん混んだ区間8P0259
  5. 格子で長方形の和をすばやく求める8P0092
  6. 差が k 以下の二つの数8P0112
  7. 掛けた素数が k 個の数を数える8P0113
  8. ネックレスから最も短く切り取る8P0155