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
nstations;a[i]people boarded at stationitoday. Answerqquestions: how many people boarded at stationsl..rin total?
1 ≤ n, q ≤ 2·10^5,1 ≤ a[i] ≤ 10^9,1 ≤ l ≤ r ≤ n.
| Sample input | Sample output |
|---|---|
8 33 1 4 1 5 9 2 62 51 86 6 |
11319 |
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).
nstations start with 0 extra people.qevents: addxextra people at every stationl..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
-
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>. -
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>. -
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>. -
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
- Range sum queries on a static array? Prefix sums: O(n) preprocessing, O(1) per query.
- Many range additions, then read the array once? Difference array: O(1) per update, O(n) to rebuild.
- Subarray sum equals k? Count pairs with
p[r] − p[l−1] = kusing a hash map of prefix values. - Why
p[0] = 0? So that ranges starting at 1 need no special case. - 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). Uselong long. - Difference arrays:
d[l] += x,d[r+1] −= x, then a running sum; sizen + 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.