Prefix Sums and Difference Arrays

The problem

You are given an array and many queries, each asking for the sum of a range. Answering each query with a loop costs O(N) per query, so Q queries cost O(NQ). With N and Q both 200,000 that is 4 × 10¹⁰ operations — far too slow.

One linear precomputation makes every query O(1).

Building the prefix array

Define pre[i] as the sum of the first i elements. Index 0 holds zero, which removes the special case for ranges that start at the beginning.

long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) {
    pre[i + 1] = pre[i] + a[i];
}

The sum of a[l..r] inclusive, with 0-based l and r, is then:

long rangeSum = pre[r + 1] - pre[l];

Everything up to r minus everything before l leaves exactly the middle.

Counting instead of summing

The same structure answers counting questions. To count elements satisfying a property in a range, build a prefix over 0/1 indicators.

// how many values in a[l..r] are even?
int[] pre = new int[n + 1];
for (int i = 0; i < n; i++) {
    pre[i + 1] = pre[i] + (a[i] % 2 == 0 ? 1 : 0);
}
int evens = pre[r + 1] - pre[l];

This generalizes: any question of the form “how many in this range” becomes O(1) if you can decide the property for a single element independently.

Two dimensions

For a grid, pre[r][c] holds the sum of the rectangle from the origin to (r-1, c-1).

long[][] pre = new long[rows + 1][cols + 1];
for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
        pre[r + 1][c + 1] = grid[r][c]
                          + pre[r][c + 1]
                          + pre[r + 1][c]
                          - pre[r][c];
    }
}

The - pre[r][c] corrects for the region counted twice by the two overlapping strips. That is inclusion-exclusion; see Inclusion-Exclusion.

Querying the rectangle from (r1, c1) to (r2, c2) inclusive uses the same correction in reverse:

long sum = pre[r2 + 1][c2 + 1]
         - pre[r1][c2 + 1]
         - pre[r2 + 1][c1]
         + pre[r1][c1];

Sketching a 3 × 3 grid and tracing the four terms by hand is worth doing once. The signs are hard to recall and easy to derive.

Difference arrays

Now reverse the problem: many range updates, then one read of the final array.

Add v to every element of a[l..r]. Do this Q times, then print the array.

Applying each update directly is O(N) per update. Instead record only where the change starts and stops.

long[] diff = new long[n + 1];

// for each update (l, r, v):
diff[l] += v;
diff[r + 1] -= v;

// after all updates, one pass reconstructs the array
long running = 0;
for (int i = 0; i < n; i++) {
    running += diff[i];
    a[i] = running;
}

Each update is O(1); the reconstruction is O(N) once. Total O(N + Q) instead of O(NQ).

The 2D version of a difference array applies a value to a whole rectangle with four point updates:

diff[r1][c1]         += v;
diff[r1][c2 + 1]     -= v;
diff[r2 + 1][c1]     -= v;
diff[r2 + 1][c2 + 1] += v;

Then take a 2D prefix sum of diff to recover the final grid.

Worked example

Given N days of rainfall and Q queries, each asking the average rainfall over a range of days.

long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + rain[i];

for (int q = 0; q < queries; q++) {
    int l = nextInt(), r = nextInt();          // 0-based, inclusive
    long total = pre[r + 1] - pre[l];
    int count = r - l + 1;
    out.printf("%.6f%n", (double) total / count);
}

Note the sum stays in long and only becomes a double at the final division. Accumulating in floating point would lose precision on large inputs for no reason.

Related