Yosunnyvim
I say whatever I want, yeah, I do whatever I want, huh

Prefix Sum & Difference Array

Published on

Prefix Sum & Difference Array

1D Prefix Sum

Given array a[1..n], build a prefix array where pref[i] = a[1] + a[2] + ... + a[i].

Sum of any range [l, r] in O(1):

sum(l, r) = pref[r] - pref[l - 1]

arr[0] = 0;
for (int i = 1; i <= n; i++) {
    arr[i] += arr[i - 1];
}
// query [l, r]:
cout << arr[r] - arr[l - 1];

This works for answering many range-sum queries after O(n) preprocessing.

Problems using this

  • A - Static Range Sum Queries
  • M. Kuriyama Mirai's Stones

Sliding Window with Prefix Sum

Find the starting index of the length-k subarray with the minimum sum.

Build prefix sum, then slide a window of size k:

arr[0] = 0;
for (int i = 1; i <= n; i++) arr[i] += arr[i - 1];

int mn = arr[k], ans = 1;
for (int i = k, j = 1; i <= n; i++, j++) {
    if (arr[i] - arr[j - 1] < mn) {
        ans = j;
        mn = arr[i] - arr[j - 1];
    }
}

Window sum = pref[i] - pref[j-1] where i - j + 1 = k.

Problems using this

  • A. Fence

Difference Array

When you have many range update queries (add d to every element in [l, r]) and then need the final array, updating each element one by one is O(n) per query — too slow.

Instead, mark the start and end of each update:

ll diff[m + 2] = {};
for (each query [x, y]) {
    diff[x] += 1;
    diff[y + 1] -= 1;
}
// how many times each operation is applied:
ll cnt[m + 1] = {};
for (int i = 1; i <= m; i++) {
    cnt[i] = cnt[i - 1] + diff[i];
}

Then for each operation i with range [l, r] and value d, applied cnt[i] times:

ll arr_diff[n + 2] = {};
for (int i = 1; i <= m; i++) {
    if (cnt[i] == 0) continue;
    int l = op[i - 1][0], r = op[i - 1][1];
    ll d = op[i - 1][2];
    arr_diff[l] += cnt[i] * d;
    arr_diff[r + 1] -= cnt[i] * d;
}
// rebuild final array with prefix sum:
for (int i = 1; i <= n; i++) {
    arr_diff2[i] = arr_diff2[i - 1] + arr_diff[i];
}

Each range update: O(1). Rebuild: O(n + m).

Problems using this

  • B. Greg and Array

2D Prefix Sum

For a grid, pref[i][j] = sum of all cells in rectangle (1,1) to (i,j).

Build with inclusion-exclusion:

pref[i][j] = grid[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];

Query sum of rectangle (x1,y1) to (x2,y2):

ans = pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];

Same idea works for counting cells (e.g. * in a forest grid).

Problems using this

  • G. Counting Rectangles — count total area of rectangles in a range
  • B - Forest Queries — count * in a sub-rectangle

Kadane’s Algorithm (Maximum Subarray Sum)

Find the maximum sum of any contiguous subarray.

Key idea: at each position, either extend the current subarray or start fresh.

ll current_sum = arr[0];
ll best_sum = arr[0];
for (int i = 1; i < n; i++) {
    if (current_sum + arr[i] > arr[i]) {
        current_sum += arr[i];   // extend
    } else {
        current_sum = arr[i];    // restart
    }
    best_sum = max(best_sum, current_sum);
}

Runs in O(n) — no prefix array needed, but it’s the same “running sum” spirit.

Problems using this

  • I. Maximum Subarray Sum

Prefix Sum + Binary Search

When you need “minimum number of elements to reach sum ≥ x”:

  1. Sort array in descending order (take largest first).
  2. Build prefix sum.
  3. Binary search on prefix array for first index where pref[mid] >= x.
sort(arr, arr + n, greater<int>());
pref[0] = arr[0];
for (int i = 1; i < n; i++) pref[i] = pref[i - 1] + arr[i];

// binary search:
int lo = 0, hi = n - 1, ans = n - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (pref[mid] >= x) { ans = mid; hi = mid - 1; }
    else lo = mid + 1;
}
cout << ans + 1;

Prefix array is sorted because we sorted the input descending.

Problems using this

  • L. Eating Queries

Prefix / Suffix Viability Check

Check if removing any single element keeps all prefix sums (or suffix sums) positive.

Compute prefix sum left-to-right; if any prefix ≤ 0 → NO. Compute suffix sum right-to-left; if any suffix ≤ 0 → NO. Otherwise YES.

ll psum = 0;
for (int i = 0; i < n - 1; i++) {
    psum += arr[i];
    if (psum <= 0) { cout << "NO"; return; }
}
ll ssum = 0;
for (int i = n - 1; i >= 1; i--) {
    ssum += arr[i];
    if (ssum <= 0) { cout << "NO"; return; }
}
cout << "YES";

Problems using this

  • D. Just Eat It!

Suffix / Distinct Count Preprocessing

Count distinct elements in suffix [i, n] for every i:

Process from right to left, track frequency:

int cnt = 0;
for (int i = n; i >= 1; i--) {
    if (freq[a[i]] == 0) cnt++;
    freq[a[i]]++;
    ans[i] = cnt;
}

Each query [l, n] → answer is ans[l] in O(1).

Problems using this

  • F. Sereja and Suffixes

2^Sort Pattern

Count subarrays of length k+1 where every consecutive pair satisfies a[i] < 2 * a[i+1].

Track consecutive “good” pairs with a running counter:

int cnt = 0, count = 0;
for (int i = 0; i < n - 1; i++) {
    if (arr[i] < 2 * arr[i + 1]) cnt++;
    else cnt = 0;
    if (cnt >= k) count++;
}

When cnt >= k, we have at least one valid subarray ending at position i+1.

Problems using this

  • J. 2^Sort
Back to top