AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Skip to content

02 Prefix sums and difference arrays / Checkpoint

Checkpoint — Prefix sums and difference arrays

45 min · +25 XP · 1 exercise · 11 questions

Exercise0/1
Quiz · 70% to clear11 q

The prefix sums checkpoint. It is timed: 45 minutes from when you start it.

What it covers. Prefix arrays and their indexes (p[r] − p[l − 1]), difference arrays (d[l] += v, d[r + 1] −= v), when each applies and when neither does, 2D prefix sums, and counting subarrays with a hash map of prefixes.

How it works. Eleven questions and one program. Clear 70% of the questions and get the program accepted. The program's timeline is a million hours long and the bookings run into the thousands, so adding each booking hour by hour runs out of time.

Before you start, make sure you can say from memory:

  • why the prefix array has a p[0] and the difference array a slot n + 1;
  • which tool fits "many queries", "many updates", and both mixed;
  • the four-term formula for a rectangle's sum.

Common questions

What does the prefix sums checkpoint test?

Building and indexing a prefix array, writing range updates into a difference array, choosing between them, 2D prefix sums, and one program — the busiest hour of a long booking timeline — judged at contest limits.

AI InterviewGet started

Prefix Sum and Difference Array Practice Test in C++

A timed 45-minute check on prefix sums and difference arrays: range-sum indexes, range updates, 2D prefix sums, and a million-hour timeline problem.

Checkpoint — Prefix sums and difference arrays is the checkpoint that closes the Prefix sums and difference arrays module: a graded quiz and whole-program exercises, passed at 70%.

Instructions

The prefix sums checkpoint. It is timed: 45 minutes from when you start it.

What it covers. Prefix arrays and their indexes (p[r] − p[l − 1]), difference arrays (d[l] += v, d[r + 1] −= v), when each applies and when neither does, 2D prefix sums, and counting subarrays with a hash map of prefixes.

How it works. Eleven questions and one program. Clear 70% of the questions and get the program accepted. The program's timeline is a million hours long and the bookings run into the thousands, so adding each booking hour by hour runs out of time.

Before you start, make sure you can say from memory:

  • why the prefix array has a p[0] and the difference array a slot n + 1;
  • which tool fits "many queries", "many updates", and both mixed;
  • the four-term formula for a rectangle's sum.

Common questions

What does the prefix sums checkpoint test?

Building and indexing a prefix array, writing range updates into a difference array, choosing between them, 2D prefix sums, and one program — the busiest hour of a long booking timeline — judged at contest limits.

Exercise

The busiest hour

A venue's timeline has hours 1 to 10⁶. Each of m bookings s e p brings p people for every hour from s to e, both included. Print the largest number of people present in any one hour, and the earliest hour at which it happens.

Constraints: 1 ≤ m ≤ 2·10⁵, 1 ≤ s ≤ e ≤ 10⁶, 1 ≤ p ≤ 10⁹.

Input: m, then m lines s e p. Output: <people> <hour>.

3
1 4 2
3 6 5
6 6 1

prints

7 3

(hours 3 and 4 hold 2 + 5 = 7 people; hour 3 is earlier.)

In this module: Prefix sums and difference arrays

← Prefix sums and difference arrays · Bit tricks for contests →