uniolympiads Ελληνικά

Prefix sums

The sum of any range in O(1)O(1) after one O(n)O(n) pass. And the reverse: many range additions with a difference array.

When

The array does not change and many queries "sum from ll to rr" arrive. With n,q≤2⋅105n, q \le 2 \cdot 10^5, O(nq)O(nq) is too slow and O(n+q)O(n + q) is comfortable.

The idea

Set P0=0P_0 = 0 and Pi+1=Pi+aiP_{i+1} = P_i + a_i. Then

al+al+1+⋯+ar=Pr+1−Pl.a_l + a_{l+1} + \dots + a_r = P_{r+1} - P_l .

The shift by one, with PP of length n+1n+1, removes the special case l=0l = 0.

In two dimensions the same works by inclusion–exclusion: the rectangle is the big rectangle from the origin, minus two strips, plus the corner that was subtracted twice.

Difference array. This is the inverse operation. To add vv to all of [l,r][l, r], write dl+=vd_l \mathrel{+}= v and dr+1−=vd_{r+1} \mathrel{-}= v. At the end, the prefix sums of dd give the array.

The move that unlocks problems

"How many subarrays have sum xx?" A subarray (l,r](l, r] has sum xx if and only if Pr−Pl=xP_r - P_l = x. Go through rr in order and count in a map how many times you have already seen Pr−xP_r - x. The same with remainders solves "sum divisible by nn".

Pitfalls

  • The sums overflow int: 2⋅105⋅109=2⋅10142 \cdot 10^5 \cdot 10^9 = 2 \cdot 10^{14}. Always long long.
  • In Subarray Divisibility, C++ % gives a negative remainder for a negative number; fix it with ((x % n) + n) % n.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/prefix-sums.cpp
// Prefix sums and difference array.
// pref[i] = a[0] + ... + a[i-1], so the sum of a[l..r] is pref[r + 1] - pref[l].

vector<ll> buildPrefix(const vector<ll>& a) {
    int n = a.size();
    vector<ll> pref(n + 1, 0);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + a[i];
    }
    return pref;
}

// Sum of a[l..r], both ends included, 0-indexed.
ll rangeSum(const vector<ll>& pref, int l, int r) {
    return pref[r + 1] - pref[l];
}

// 2D: pref2[i][j] = sum of the rectangle with corners (0, 0) and (i - 1, j - 1).
vector<vector<ll>> buildPrefix2D(const vector<vector<ll>>& a) {
    int n = a.size();
    int m = 0;
    if (n > 0) {
        m = a[0].size();
    }
    vector<vector<ll>> pref(n + 1, vector<ll>(m + 1, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            pref[i + 1][j + 1] = a[i][j] + pref[i][j + 1] + pref[i + 1][j] - pref[i][j];
        }
    }
    return pref;
}

// Sum of the rectangle rows r1..r2, columns c1..c2 (inclusive).
ll rectSum(const vector<vector<ll>>& pref, int r1, int c1, int r2, int c2) {
    return pref[r2 + 1][c2 + 1] - pref[r1][c2 + 1] - pref[r2 + 1][c1] + pref[r1][c1];
}

// Difference array: many "add v to a[l..r]" updates, then one pass to read the result.
struct DiffArray {
    vector<ll> d;

    DiffArray(int n) : d(n + 1, 0) {}

    void addRange(int l, int r, ll v) {
        d[l] += v;
        d[r + 1] -= v;
    }

    vector<ll> result() {
        int n = (int)d.size() - 1;
        vector<ll> a(n, 0);
        ll running = 0;
        for (int i = 0; i < n; i++) {
            running += d[i];
            a[i] = running;
        }
        return a;
    }
};

Tested on 2,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.