{ }codelper

Learn › C#

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.

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);    }}
stdin
6 3 16
5 1 9 2 7 4
1 6
2 4
3 3
stdout
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" in prefix[i] ahead of time.
    For 5 1 9 2 7 4 the table is 0 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 left and the right end right of a range.
    Move right one step to add a number; while the sum is at least s, record the length and move left one 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

PythonMake 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
JavaScriptnew 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
TypeScriptSame as JavaScript.
The table's type is number[]
Javalong[] 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
Clong long prefix[10001]; placed outside any function is filled with 0.
Print with %lld
Craykonprefix = 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 -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.

Practice

  1. Merge the logs of two entrances8P0260
  2. Fast range sums8P0039
  3. Two numbers summing to S in a sorted list8P0069
  4. The busiest stretch of the bus8P0259
  5. Fast rectangle sums on a grid8P0092
  6. Pairs within k8P0112
  7. Count numbers with k prime factors8P0113
  8. Cutting the shortest piece from a necklace8P0155