Card 06/ 08
Reading a Range With p[j] − p[i]
The prefix array is one longer than the input, so the range from i to j inclusive ends at p[j + 1], and p[j] drops the last element.
Reading the range from i to j inclusive as p[j] − p[i] drops its last element, because the prefix array is shifted one place from the input. p[i] is the sum of the first i elements, the ones before index i, so the total up to and including j is p[j + 1], not p[j]. The start needs no shift: subtracting p[i] removes exactly the elements before i.
On 2 6 1 4 3, with p = 0 2 8 9 13 16, the range 1 to 3 is 6 1 4, which sums to 11. p[3] − p[1] gives 7, the sum of 6 1, with the 4 dropped.
The second wrong form comes from a prefix array with no leading 0, where q[i] includes element i. There q[j] − q[i − 1] is right for every i but 0, and at i = 0 it reads q[−1]. The listing reads both, on the values 2 6 1 4 3.
values = [2, 6, 1, 4, 3]
prefix = [0, 2, 8, 9, 13, 16]
i, j = 1, 3
print(f"indices {i} to {j}: p[j] - p[i] = {prefix[j] - prefix[i]}, p[j + 1] - p[i] = {prefix[j + 1] - prefix[i]}, true sum {sum(values[i:j + 1])}")
inclusive = [2, 8, 9, 13, 16]
i, j = 0, 2
print(f"no leading 0, indices {i} to {j}: p[i - 1] is {inclusive[i - 1]}, p[j] - p[i - 1] = {inclusive[j] - inclusive[i - 1]}, true sum {sum(values[i:j + 1])}")indices 1 to 3: p[j] - p[i] = 7, p[j + 1] - p[i] = 11, true sum 11
no leading 0, indices 0 to 2: p[i - 1] is 16, p[j] - p[i - 1] = -7, true sum 9Python reads q[−1] as the last entry, 16, so the range 0 to 2 comes out as −7 with no error. The same read behaves differently in each language:
| Language | q[−1] at i = 0 | q[2] − q[−1] |
|---|---|---|
| Python | 16, the last entry | −7, no error |
| Java | ArrayIndexOutOfBoundsException | never computed |
| TypeScript | undefined | NaN, no error |
Only Java stops; Python and TypeScript return a wrong number. The leading 0 removes the case: with p[0] = 0, the formula p[j + 1] − p[i] reads p[0] when i is 0 and needs no branch. Say what p[i] means before writing the read, and the formula follows from it: the sum before index i, so a range ends at p[j + 1].
← → move through sections and cards