§ Subarrays ~= prefixes

To solve any problem about subarrays, we can reinterpret a subarray [l..r] as a prefix [0..r] - [0..l]. For example, to find all subarrays [l..r] whose sum of elements divides n, we can think of this as finding a subarray [l..r] where the sum of elements modulo n is zero. This is CSES' subarray divisibiity problem:

int main() {
    int n;
    cin >> n;
    vector<ll> xs(n);
    for (int i = 0; i < n; ++i) {
        cin >> xs[i]; xs[i] = xs[i] % n; if (xs[i] < 0) { xs[i] += n; }
    }

    ll count = 0; // number of subarrays with sum = 0 (mod n)
    ll cursum = 0; //  current sum [0..i]
    // number of subarrays [0..r] (for some r) such that Σa[i] = count.
    map<ll, ll> partial_sum_count;
    partial_sum_count[0] = 1;

    for (int i = 0; i < n; ++i) {
        // current sum [0..i]
        cursum = (cursum + xs[i]) % n;

        // for each [0..j] (for j < i) with sum cursum, we want:
        // sum([i..j]) = 0
        // => sum([0..i]) - sum([0..j)) = 0
        // => sum([0..i]) = sum([0..j))
        // for each such `j`, we get one subarray.
        auto it = partial_sum_count.find(cursum);
        if (it != partial_sum_count.end()) {
            count += it->second;
        }

        // partial sum [0..i] = cursum
        partial_sum_count[cursum]++;
    }

    cout << count << "\n";

    return 0;
}