A program needs sums of consecutive elements of an integer array a. Each request gives indices l and r, with 0 <= l <= r < n, and asks for the sum of a[l] through a[r], including both ends.
The array has n initialized elements, where 1 <= n <= 1000000. Values may be negative. Assume all the additions and subtractions shown below fit in int.
The direct method reads the requested elements each time:
int interval_sum(int *a, int l, int r) {
int result = 0;
for (int i = l; i <= r; ++i) result += a[i];
return result;
}A proposed alternative first creates an extra array p of length n + 1. It keeps a as well.
void build(int *a, int *p, int n) {
p[0] = 0;
for (int i = 0; i < n; ++i)
p[i + 1] = p[i] + a[i];
}After calling build once, the alternative answers each request with this function:
int stored_sum(int *p, int l, int r) {
return p[r + 1] - p[l];
}Consider two uses in which a stays unchanged:
| Case | Array | Requests |
|---|---|---|
| A | 1000000 elements | 100000 sums, each covering most of the array |
| B | 1000000 elements | One sum of three consecutive elements |
For comparing work, count each integer read, write, addition, or subtraction as one step. There is enough memory for p. You do not need exact step counts or special notation for running time.
Changing the array. In case C, a request can instead replace a[k] with new_value, where 0 <= k < n. Sum requests and replacements may occur in any order, including several replacements of the same element. Every sum must use the current values in a.
The following proposal calls build once at the start, uses replace for every replacement, and uses stored_sum for every sum request:
void replace(int *a, int *p, int k, int new_value) {
int change = new_value - a[k];
a[k] = new_value;
p[k + 1] += change;
}When replacements are rare. In a separate workload, there are 1000000 array elements, 100000 sum requests, and fewer than 10 replacement requests in total. Each sum request may cover most of the array. Replacements can occur between any two sum requests, and the same element may be replaced more than once. The new values are not known in advance.
A developer claims that this workload can be handled efficiently despite the replacements. The developer is allowed to change how replacements and queries are handled, while keeping every result correct. There is enough memory for a and p, and for a small amount of additional information. Compare the total work with scanning most of the million-element array separately for every sum request.
A different kind of question. The program may also be asked for the largest element between l and r. A proposed table m stores the largest element from the beginning of a: for j > 0, m[j] is the largest of a[0] through a[j - 1]. Set m[0] to the smallest value of type int. A query would have access to just m[l] and m[r + 1], as the sum query has access to two entries of p.