Prefix Sums
Prefix sums: answering "sum on a segment" in O(1); the difference array.
The setting: an array of n numbers and q queries "what is the sum from the l-th to the r-th element?". Computing every query with a loop is O(n·q): at n = q = 10⁵ that is 10¹⁰ operations — hopeless.
The solution is precomputation. Build a prefix-sum array: p[i] = the sum of the first i elements. Then the sum on the segment [l, r] is simply p[r] - p[l-1]: from "the sum up to r" we subtracted "the sum up to l-1". Each query is O(1), everything together — O(n + q).
Enter: 5 2, the array 1 2 3 4 5, then the queries: 2 4 and 1 5
Details worth remembering:
• 1-based indexing with p[0] = 0 removes the special case l = 1;
• prefix sums accumulate in long long — the sum of a hundred thousand billions won't fit in an int;
• the same idea works in 2D: a prefix table answers rectangle-sum queries in O(1).
The mirror trick is the difference array: when the queries instead MODIFY segments ("add x to everyone from l to r") and the answer is needed once at the end, store differences: d[l] += x, d[r+1] -= x, and at the end restore the array with prefix sums of those differences.
The difference array. Enter: 5 2, then the queries "1 3 2" and "2 5 1"
Task: using a prefix-sum array, count the segments with zero sum (hint: the sum of [l, r] is zero when p[r] == p[l-1]; count equal prefixes with a map — two topics combined!).
Mark the lesson as completed and move on to binary search.