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.
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 abouta[0..i]ora[1..i]. Tomorrow's lesson. - Frequency.
freq[x]++if values are small. Ifa_iis 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.
function counts(nums) {
const freq = new Map();
for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
return freq;
}Checks 0/2