Algorithms · 29
Prefix sums and two pointers
Get the sum of any range with one subtraction, and find a range by moving two positions forward only.
A prefix sum table writes down the running total from the front.
Two pointers is a way to find an answer by moving two positions over a list.
The example below takes 6 numbers, answers 3 questions of the form "the sum from the l-th to the r-th", and finds the length of the shortest contiguous range whose sum is at least 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;}첫줄 = Console.ReadNumbers();n = 첫줄[0];q = 첫줄[1];s = 첫줄[2];a = Console.ReadNumbers(); // prefix[i] = 앞에서 i개의 합 (prefix[0] = 0)prefix = NewList(n + 1, 0);for (i = 0; i < n; i++){ prefix[i + 1] = prefix[i] + a[i];} for (k = 0; k < q; k++){ lr = Console.ReadNumbers(); l = lr[0]; r = lr[1]; Console.WriteLine(prefix[r] - prefix[l - 1]); // l번째부터 r번째까지의 합} // 합이 s 이상인 가장 짧은 이어진 구간: left와 right는 앞으로만 간다best = 0;left = 0;window = 0;for (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);6 3 16 5 1 9 2 7 4 1 6 2 4 3 3
28 12 9 3
Key points
- Adding from scratch for every question repeats the same additions.
So store "the sum of the first i numbers" inprefix[i]ahead of time.
For5 1 9 2 7 4the table is0 5 6 15 17 24 28. - The sum from the l-th to the r-th is
prefix[r] - prefix[l - 1].
Take the sum of the first r numbers, remove the first l − 1, and only the part in between is left.
The table is built once, and each question costs one subtraction. - Make the table one slot longer (n + 1 slots) with
prefix[0] = 0, and the same formula works even when l is 1. - Two pointers holds the left end
leftand the right endrightof a range.
Moverightone step to add a number; while the sum is at least s, record the length and moveleftone step to remove a number. - Neither position ever moves back, so each moves at most n times.
You don't have to try every range because all the numbers are positive: growing the range makes the sum larger and shrinking it makes the sum smaller. - With values around one billion, adding just three goes past a 32-bit integer (up to about 2.1 billion).
Use 64 bits for the table and for any variable that holds a sum.
How each language writes it
| Python | Make prefix = [0] * (n + 1), then prefix[i + 1] = prefix[i] + a[i].list(itertools.accumulate(a, initial=0)) builds the same table.Integers have no size limit |
|---|---|
| JavaScript | new Array(n + 1).fill(0).Numbers are exact up to 2^53 (about 9 quadrillion), so the sum of tens of thousands of billion-sized values still fits |
| TypeScript | Same as JavaScript. The table's type is number[] |
| Java | long[] prefix = new long[n + 1]; — a new array is filled with 0.Variables that hold a sum are long too |
| C# | long[] prefix = new long[n + 1]; — a new array is filled with 0.Variables that hold a sum are long too |
| C++ | std::vector<long long> prefix(n + 1, 0);.Variables that hold a sum are long long too |
| C | long long prefix[10001]; placed outside any function is filled with 0.Print with %lld |
| Craykon | prefix = NewList(n + 1, 0);.Numbers are exact up to 2^53. The loop that shrinks the range is while (window >= s) { } |
Common mistakes
Subtracting 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 — the 2nd number, 1, was subtracted too. The right answer is 12
Subtract prefix[l - 1].
The l-th number has to stay, so remove only the l − 1 numbers before it.
Keeping prefix sums in an 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 — 3 billion does not fit in an int (up to about 2.1 billion), so it overflowed
Make the table and the sum variables long (long long in C and C++).
Each value may fit in an int while the sum does not.
Shrinking the range with if instead of 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 — the right answer is 1, the range holding just the 10. Shrinking only one step per lap, left never caught up
The range must keep shrinking while the sum is at least s, so write while.
How languages differ
Use prefix sums when a list does not change and you are asked for many sums.
This two-pointer way of watching a sum is correct only when all the numbers are positive.
With negative numbers, growing the range can make the sum smaller: looking for a range with sum at least 5 in
Decide first whether you count from 0 or from 1, and trace a small example by hand.
Use prefix sums when a list does not change and you are asked for many sums.
This two-pointer way of watching a sum is correct only when all the numbers are positive.
With negative numbers, growing the range can make the sum smaller: looking for a range with sum at least 5 in
-1 5, it misses the single 5 and prints 0.Decide first whether you count from 0 or from 1, and trace a small example by hand.