算法 · 29
前缀和与双指针
用一次减法求出区间和；让两个位置只向前移动来寻找区间。
前缀和是把从头累加的结果记在一张表里。
双指针是在列表上移动两个位置来寻找答案的方法。
下面的例子对 6 个数回答 3 个“第 l 个到第 r 个的和”的询问，并求出和不小于 16 的最短连续区间的长度。
n, q, s = map(int, input().split())a = list(map(int, input().split())) # prefix[i] = 앞에서 i개의 합 (prefix[0] = 0)prefix = [0] * (n + 1)for i in range(n): prefix[i + 1] = prefix[i] + a[i] for _ in range(q): l, r = map(int, input().split()) print(prefix[r] - prefix[l - 1]) # l번째부터 r번째까지의 합 # 합이 s 이상인 가장 짧은 이어진 구간: left와 right는 앞으로만 간다best = 0left = 0window = 0for right in range(n): window += a[right] while window >= s: if best == 0 or right - left + 1 < best: best = right - left + 1 window -= a[left] left += 1print(best)const t = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q, s] = t;const a = t.slice(3, 3 + n); // prefix[i] = 앞에서 i개의 합 (prefix[0] = 0)const prefix = 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);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);import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(), q = in.nextInt(); long s = in.nextLong(); long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = in.nextLong(); // prefix[i] = 앞에서 i개의 합 (prefix[0] = 0). 합은 int를 넘을 수 있어 long long[] prefix = new long[n + 1]; for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + a[i]; for (int k = 0; k < q; k++) { int l = in.nextInt(), r = in.nextInt(); System.out.println(prefix[r] - prefix[l - 1]); // l번째부터 r번째까지의 합 } // 합이 s 이상인 가장 짧은 이어진 구간: left와 right는 앞으로만 간다 int best = 0, left = 0; long window = 0; for (int 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++; } } System.out.println(best); }}using System; class Program{ static void Main() { string[] first = Console.ReadLine().Split(); int n = int.Parse(first[0]), q = int.Parse(first[1]); long s = long.Parse(first[2]); long[] a = Array.ConvertAll(Console.ReadLine().Split(), long.Parse); // prefix[i] = 앞에서 i개의 합 (prefix[0] = 0). 합은 int를 넘을 수 있어 long long[] prefix = new long[n + 1]; for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + a[i]; for (int k = 0; k < q; k++) { string[] lr = Console.ReadLine().Split(); int l = int.Parse(lr[0]), r = int.Parse(lr[1]); Console.WriteLine(prefix[r] - prefix[l - 1]); // l번째부터 r번째까지의 합 } // 합이 s 이상인 가장 짧은 이어진 구간: left와 right는 앞으로만 간다 int best = 0, left = 0; long window = 0; for (int 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.WriteLine(best); }}#include <iostream>#include <vector> int main() { int n, q; long long s; std::cin >> n >> q >> s; std::vector<long long> a(n); for (int i = 0; i < n; i++) std::cin >> a[i]; // prefix[i] = 앞에서 i개의 합 (prefix[0] = 0). 합은 int를 넘을 수 있어 long long std::vector<long long> prefix(n + 1, 0); for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + a[i]; for (int k = 0; k < q; k++) { int l, r; std::cin >> l >> r; std::cout << prefix[r] - prefix[l - 1] << '\n'; // l번째부터 r번째까지의 합 } // 합이 s 이상인 가장 짧은 이어진 구간: left와 right는 앞으로만 간다 int best = 0, left = 0; long long window = 0; for (int 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++; } } std::cout << best << '\n';}#include <stdio.h> long long a[10000], prefix[10001]; int main(void) { int n, q; long long s; scanf("%d %d %lld", &n, &q, &s); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); // prefix[i] = 앞에서 i개의 합 (prefix[0] = 0). 합은 int를 넘을 수 있어 long long for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + a[i]; for (int k = 0; k < q; k++) { int l, r; scanf("%d %d", &l, &r); printf("%lld\n", prefix[r] - prefix[l - 1]); // l번째부터 r번째까지의 합 } // 합이 s 이상인 가장 짧은 이어진 구간: left와 right는 앞으로만 간다 int best = 0, left = 0; long long window = 0; for (int 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++; } } printf("%d\n", best); return 0;}첫줄 = 控制台.读数字();n = 첫줄[0];q = 첫줄[1];s = 첫줄[2];a = 控制台.读数字(); // prefix[i] = 앞에서 i개의 합 (prefix[0] = 0)prefix = 新列表(n + 1, 0);循环 (i = 0; i < n; i++){ prefix[i + 1] = prefix[i] + a[i];} 循环 (k = 0; k < q; k++){ lr = 控制台.读数字(); l = lr[0]; r = lr[1]; 控制台.输出(prefix[r] - prefix[l - 1]); // l번째부터 r번째까지의 합} // 합이 s 이상인 가장 짧은 이어진 구간: left와 right는 앞으로만 간다best = 0;left = 0;window = 0;循环 (right = 0; right < n; right++){ window += a[right]; 当 (window >= s) { 如果 (best == 0 || right - left + 1 < best) { best = right - left + 1; } window -= a[left]; left++; }}控制台.输出(best);6 3 16 5 1 9 2 7 4 1 6 2 4 3 3
28 12 9 3
要点
- 每次询问都从头加一遍，就是在重复同样的加法。
所以先把“前 i 个数的和”记在prefix[i]里。
数是5 1 9 2 7 4时，表是0 5 6 15 17 24 28。 - 第 l 个到第 r 个的和是
prefix[r] - prefix[l - 1]。
从前 r 个的和里去掉前 l − 1 个，剩下的正好是中间这一段。
表只建一次，每个询问只要一次减法。 - 把表多开一格（n + 1 格）并令
prefix[0] = 0，l 为 1 时也能直接用同一个式子。 - 双指针记着区间的左端
left和右端right。right向右走一格把数加进来；只要和不小于 s，就记录长度，再让left走一格把数减掉。 - 两个位置都不会往回走，所以各自最多移动 n 次。
之所以不必把所有区间都试一遍，是因为数全是正数：区间变长和就变大，变短和就变小。 - 数值在 10 亿左右时，只加三个就超过 32 位整数（最大约 21 亿）。
保存和的变量和表都要用 64 位。
各语言的写法
| Python | 先建 prefix = [0] * (n + 1)，再 prefix[i + 1] = prefix[i] + a[i]。list(itertools.accumulate(a, initial=0)) 也能得到同一张表。整数没有大小限制 |
|---|---|
| JavaScript | new Array(n + 1).fill(0)。数在 2^53（约 9 千万亿）以内都是精确的，几万个 10 亿左右的值相加也放得下 |
| TypeScript | 和 JavaScript 一样。 表的类型是 number[] |
| Java | long[] 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 |
| C | 把 long long prefix[10001]; 放在函数外面，里面全是 0。输出用 %lld |
| Craykon | prefix = 新列表(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 个。
缩短区间时用了 if 而不是 while
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。每轮只缩短一格，left 跟不上
只要和不小于 s 就要一直缩短，所以要写 while。
把前缀和放进了 intJava · 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，和却可能溢出。
各语言的差异
列表的值不再变化、又要多次求和时，就用前缀和。
用双指针盯着和的这种做法，只在所有数都是正数时才正确。
混入负数后，区间变长和反而可能变小：在
先定好下标从 0 数还是从 1 数，再拿一个小例子手动走一遍。
列表的值不再变化、又要多次求和时，就用前缀和。
用双指针盯着和的这种做法，只在所有数都是正数时才正确。
混入负数后，区间变长和反而可能变小：在
-1 5 中找和不小于 5 的区间，它会漏掉单独的 5 而输出 0。先定好下标从 0 数还是从 1 数，再拿一个小例子手动走一遍。