B.5.QD:5.3 - A successful cumulative computation opens an interval question

A program can construct cumulative totals for an integer array a. It starts with S[0] = 0 and sets S[i+1] = S[i] + a[i]. For a = [2,-1,3,4], the result is S = [0,2,1,4,8].

The original task needed the total 8. Recovering the operation reveals that each S[i] already gives the sum before position i. This opens the question: Can we answer many interval-sum queries from the same cumulative totals?

Specify an interval by indices l and r, with 0 ≤ l ≤ r ≤ n; it includes l and ends just before r. Splitting the first r elements at l gives S[r] = S[l] + sum(a[l],…,a[r-1]). Hence the interval sum is S[r] - S[l]. For the last two elements, l = 2 and r = 4, so the answer is 8 - 1 = 7. For l = r the answer is 0.

This is a general derivation under integer arithmetic with enough capacity to avoid overflow. Each query uses two stored totals and one subtraction after the array has been prepared. Whether preparation is worthwhile depends on how many queries and changes the application requires.

If a[i] changes by d, every S[j] with j > i changes by d. Frequent changes therefore open a further question: which data organization supports the required mixture of updates and interval queries? That question can be developed when the workload makes it relevant. The successful cumulative operation already answers the unchanged-array question.