Arrays as the Contest Workbench

If graphs are the late-game language of competitive programming, arrays are the native tongue. You will spend hundreds of hours walking indices, building frequency tables, and arguing with off-by-one errors.

Treat an array as a workbench: a place you lay down intermediate facts so the next pass is O(1) or O(log n) instead of another scan.

1-based prefix in C++ — index 0 is a sentinelcpp

vector<long long> pref(n + 1);
for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i];
// sum of a[l..r] inclusive, 1-based:
long long range = pref[r] - pref[l - 1];

Three arrays you will build constantly:

- Prefix / suffix. pref[i] is an answer about a[0..i] or a[1..i]. Tomorrow's lesson. - Frequency. freq[x]++ if values are small. If a_i is up to 10⁹, you use a hash map instead of a 10⁹-sized table. - Position index. where[value] = i (or a vector of positions) so you can jump instead of search.

CHECK

You have n ≤ 2·10⁵ numbers, each between 1 and 10⁹. You need, for each value, the list of indices where it appears. What do you allocate?

TRACE

A classic exclusive/inclusive bug. Watch the last index.

The task

Reverse the subarray a[l..r] inclusive, 0-based, in place. l = 1, r = 3, a = [9, 1, 4, 8, 2]. Expected: [9, 8, 4, 1, 2].

inclusive r means r is a live element

1 / 3

Frequency map in the arena language (JavaScript)js

function counts(nums) {
  const freq = new Map();
  for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
  return freq;
}

CHECK

You iterate for (let i = 0; i < n; i++) and read a[i + 1]. When is this defined?

Checks 0/2

Next lesson