SyntaxPilot
Courses/Competitive Programming/Lesson 7

Competitive Programming · Lesson 7 of 90 · 11 min

Prefix sums and difference arrays

queued

These are the notes for Competitive Programming episode 7, the course's first big technique. An original problem, Metro Footfall, asks for many range sums; the brute force hits the time limit on a max test, and a cricket-scoreboard idea fixes it: prefix sums, where any range sum is one subtraction. Then the reverse problem, Festival Rush, asks for many range updates; a bus conductor's trick fixes it: the difference array. You also see the two classic prefix-sum bugs with their real outputs. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The problem: Metro Footfall

Problem G · Metro Footfall (written for this course). A metro line has n stations; a[i] people boarded at station i today. Answer q questions: how many people boarded at stations l..r in total?

1 ≤ n, q ≤ 2·10^5, 1 ≤ a[i] ≤ 10^9, 1 ≤ l ≤ r ≤ n.

Sample input Sample output
8 3
3 1 4 1 5 9 2 6
2 5
1 8
6 6
11
31
9

Brute force: loop over every range

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (q--) {
        int l, r;
        cin >> l >> r;
        ll sum = 0;
        for (int i = l; i <= r; i++) sum += a[i];
        cout << sum << '\n';
    }
    return 0;
}

The sample gives 11 31 9: correct. But each question can cost n steps: n·q = 2·10^5 · 2·10^5 = 4·10^10.

A max test made in code

You can't paste 4 lakh numbers into an input box, so this program builds the worst case itself and times it with chrono:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 200000, q = 200000;   // a max test, made in code
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = i % 100 + 1;
    auto start = chrono::steady_clock::now();
    ll total = 0;
    for (int k = 0; k < q; k++) {
        int l = 1 + k % 10, r = n - k % 10;
        ll sum = 0;
        for (int i = l; i <= r; i++) sum += a[i];
        total += sum;
    }
    auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
    cout << "total " << total << ", time " << ms << " ms\n";
    return 0;
}

Result in the SyntaxPilot compiler: Time Limit Exceeded (stopped after 8 seconds; a judge allows 1-2).

The idea: a cricket scoreboard

In a cricket match In code
The score after each over: 45 after 10, 112 after 20 p[i] = a[1] + … + a[i], the running total
Runs in overs 11-20 = 112 − 45 = 67, no recount sum(l..r) = p[r] − p[l−1], one subtraction
The score before the first ball is 0 p[0] = 0, so l = 1 works too

Prefix sums

p[0] = 0
p[i] = p[i−1] + a[i]          for i = 1..n
sum(l..r) = p[r] − p[l−1]

On the sample:

i 0 1 2 3 4 5 6 7 8
a[i] 3 1 4 1 5 9 2 6
p[i] 0 3 4 8 9 14 23 25 31

Stations 2..5: p[5] − p[1] = 14 − 3 = 11. Stations 1..8: p[8] − p[0] = 31. Station 6: p[6] − p[5] = 9.

Why l − 1? p[r] covers 1..r. You want to remove 1..l−1, which is p[l−1]. Subtracting p[l] would also remove station l itself.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<ll> p(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        p[i] = p[i - 1] + x;
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << p[r] - p[l - 1] << '\n';
    }
    return 0;
}

Sample → 11 31 9. The same max test with a prefix array (build p, then total += p[r] - p[l - 1]) printed total 2019925300000, time 1 ms: the same total as the brute force would compute, in about a millisecond.

Two classic bugs (real outputs)

Off by one: cout << p[r] - p[l] << '\n';

10
28
0

Every answer is missing station l (1, 3 and 9 respectively).

Overflow: vector<int> p(n + 1, 0); with input 3 1 / 1000000000 1000000000 1000000000 / 1 3:

-1294967296

An int holds up to 2,147,483,647; the running total reaches 3·10^9 and wraps around. The largest prefix is n · max a = 2·10^14: use long long.

Limitation: prefix sums assume the array does not change between queries. Mixed updates and queries need a Fenwick tree or a segment tree (later in this course).

The reverse problem: Festival Rush

Problem G2 · Festival Rush (written for this course). n stations start with 0 extra people. q events: add x extra people at every station l..r. After all events, print the extra crowd at each station.

Sample: n = 6, events (1,3,+2), (2,5,+3), (4,6,+1) → 2 5 5 4 4 1.

Looping l..r per event is O(n·q) again.

The idea: a bus conductor

On a bus In code
A group of 3 boards at stop 2: write +3 at stop 2 d[l] += x
They get off after stop 5: write −3 at stop 6 d[r + 1] -= x
People on the bus at stop k = sum of marks 1..k prefix sum of d

Difference array

for each event (l, r, x):   d[l] += x;   d[r + 1] -= x;
final[i] = d[1] + d[2] + … + d[i]     (a running sum)

On the sample:

i 1 2 3 4 5 6 7
d[i] 2 3 0 −1 0 −3 −1
running sum 2 5 5 4 4 1

d[4] = −2 + 1: the first event stops there and the third starts there. d[7] is index n + 1, so d needs n + 2 slots.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<ll> d(n + 2, 0);
    while (q--) {
        int l, r;
        ll x;
        cin >> l >> r >> x;
        d[l] += x;
        d[r + 1] -= x;
    }
    ll cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += d[i];
        cout << cur << " \n"[i == n];
    }
    return 0;
}

Input 6 3 / 1 3 2 / 2 5 3 / 4 6 1 → 2 5 5 4 4 1.

" \n"[i == n] is a contest idiom: the string " \n" has two characters; i == n is 0 or 1, so it picks a space after every number and a newline after the last.

Bug, caught live: with vector<ll> d(n + 1, 0); and #define _GLIBCXX_DEBUG on the first line, the event ending at station 6 writes d[7]:

Error: attempt to subscript container with out-of-bounds index 7, but 
container only holds 7 elements.

Solutions in C++, Java and Python (Metro Footfall)

C++: the prefix-sum program above.

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken());
        long[] p = new long[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) p[i] = p[i - 1] + Long.parseLong(st.nextToken());
        StringBuilder out = new StringBuilder();
        while (q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken()), r = Integer.parseInt(st.nextToken());
            out.append(p[r] - p[l - 1]).append('\n');
        }
        System.out.print(out);
    }
}

Python

import sys
from itertools import accumulate

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    p = [0] + list(accumulate(int(x) for x in data[2:2 + n]))
    out = []
    pos = 2 + n
    for _ in range(q):
        l, r = int(data[pos]), int(data[pos + 1])
        pos += 2
        out.append(p[r] - p[l - 1])
    print("\n".join(map(str, out)))

main()

Brute force vs optimal

Brute force Prefix sums Difference array
Query / update loop l..r: O(n) O(1) O(1) per update
Preprocessing none O(n) build O(n) final sweep
Total at n = q = 2·10^5 4·10^10 (TLE) 4·10^5 4·10^5
Extra memory O(1) n + 1 long longs n + 2 long longs

Common mistakes (and the real messages)

Mistake What you see Why Fix
p[r] - p[l] 10 28 0 instead of 11 31 9 removes station l p[r] - p[l - 1]
vector<int> p -1294967296 prefix exceeds 2.1·10^9 vector<ll> p
vector<ll> d(n + 1) out-of-bounds index 7, but container only holds 7 elements (with _GLIBCXX_DEBUG) d[r + 1] with r = n size n + 2
0-based array with 1-based queries wrong answers or index −1 p[l − 1] with l = 0 store from index 1, keep p[0] = 0
Prefix sums while the array changes wrong answers p is stale updates first, or a Fenwick/segment tree

Mini project: crowd report

Combine both ideas: read Festival Rush events, build the final crowd with a difference array, then answer range-sum questions on the result with a prefix array. Input: n q k, then q events l r x, then k questions l r. Each step is O(1) per event or question.

Practice

  1. Count even numbers in a[l..r] for many queries.

    Answer Prefix count: <code>c[i] = c[i−1] + (a[i] % 2 == 0)</code>; answer <code>c[r] − c[l−1]</code>.

  2. A 0-based array: write the range sum of a[l..r] (0-based, inclusive).

    Answer With <code>p</code> of size n+1 and <code>p[i+1] = p[i] + a[i]</code>: <code>p[r+1] − p[l]</code>.

  3. Average boarded at stations l..r, printed with 2 decimals.

    Answer <code>(double)(p[r] − p[l−1]) / (r − l + 1)</code>, printed with <code>fixed << setprecision(2)</code>.

  4. How many subarrays have sum exactly 0? (Hint: two equal prefix values.)

    Answer <code>sum(l..r) = 0</code> exactly when <code>p[r] = p[l−1]</code>. Count equal pairs among p[0..n] with a map: O(n log n).

Quick quiz

a[1..6] = 2 7 1 8 2 8 and p is its prefix sum array. What is p[5] − p[2]?

A) 11 · B) 18 · C) 13 · D) 20

Answer

A. p[5] − p[2] = a[3] + a[4] + a[5] = 1 + 8 + 2 = 11. It starts at index 3: that's why sum(l..r) uses p[l − 1].

Interview questions

  1. Range sum queries on a static array? Prefix sums: O(n) preprocessing, O(1) per query.
  2. Many range additions, then read the array once? Difference array: O(1) per update, O(n) to rebuild.
  3. Subarray sum equals k? Count pairs with p[r] − p[l−1] = k using a hash map of prefix values.
  4. Why p[0] = 0? So that ranges starting at 1 need no special case.
  5. When do prefix sums stop working? When updates and queries interleave; use a Fenwick tree or segment tree.

Glossary

Term Meaning Example
Range query A question about a block l..r of an array total of stations 2..5
Prefix The first i elements of an array a[1..i]
Prefix sum array p[i] = sum of the first i elements p = 0 3 4 8 9 …
Range update Change every element in l..r add 3 to stations 2..5
Difference array Marks +x at l and −x at r+1; its running sum is the array d[2] += 3, d[6] -= 3
Running sum Adding values one by one, keeping the total 2, 5, 5, 4, 4, 1
1-indexed Positions counted from 1 station 1 is a[1]
Off-by-one error An index or bound wrong by exactly one p[l] instead of p[l−1]
Overflow A value too big for its type wraps around int total → -1294967296
Max test An input at the largest allowed size n = q = 2·10^5
chrono C++ library for measuring time steady_clock::now()
Static array An array that does not change between queries Metro Footfall

Summary

  • Looping over each range costs O(n·q): TLE at 2·10^5 × 2·10^5.
  • Prefix sums: p[0] = 0, p[i] = p[i−1] + a[i], sum(l..r) = p[r] − p[l−1]; O(n + q). Use long long.
  • Difference arrays: d[l] += x, d[r+1] −= x, then a running sum; size n + 2; O(n + q).
  • They are two sides of one idea: a running total turns ranges into their endpoints.

Next episode: 2D prefix sums and 2D difference arrays: rectangle sums and rectangle updates on a grid.