uniolympiads English

Αθροίσματα προθεμάτων

Άθροισμα οποιουδήποτε διαστήματος σε O(1)O(1), μετά από ένα πέρασμα O(n)O(n). Και το αντίστροφο: πολλές προσθέσεις σε διαστήματα με τον πίνακα διαφορών.

Πότε

Ο πίνακας δεν αλλάζει και έρχονται πολλά ερωτήματα «άθροισμα από ll ως rr». Με n,q≤2⋅105n, q \le 2 \cdot 10^5 το O(nq)O(nq) δεν περνά, το O(n+q)O(n + q) περνά άνετα.

Η ιδέα

Ορίζουμε P0=0P_0 = 0 και Pi+1=Pi+aiP_{i+1} = P_i + a_i. Τότε

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

Η μετατόπιση κατά ένα, με PP μήκους n+1n+1, γλιτώνει την ειδική περίπτωση l=0l = 0.

Σε δύο διαστάσεις ισχύει το ίδιο με εγκλεισμό–αποκλεισμό: το ορθογώνιο είναι το μεγάλο ορθογώνιο από την αρχή, μείον δύο λωρίδες, συν τη γωνία που αφαιρέθηκε δύο φορές.

Πίνακας διαφορών. Είναι η αντίστροφη πράξη. Για να προσθέσεις vv σε όλο το [l,r][l, r], γράφεις dl+=vd_l \mathrel{+}= v και dr+1−=vd_{r+1} \mathrel{-}= v. Στο τέλος τα αθροίσματα προθεμάτων του dd δίνουν τον πίνακα.

Η κίνηση που ξεκλειδώνει προβλήματα

«Πόσα διαστήματα έχουν άθροισμα xx;» Ένα διάστημα (l,r](l, r] έχει άθροισμα xx αν και μόνο αν Pr−Pl=xP_r - P_l = x. Περνάς τα rr με τη σειρά και μετράς σε ένα map πόσες φορές έχεις ήδη δει το Pr−xP_r - x. Το ίδιο, με υπόλοιπα, λύνει το «άθροισμα διαιρετό με nn».

Παγίδες

  • Τα αθροίσματα ξεπερνούν το int: 2⋅105⋅109=2⋅10142 \cdot 10^5 \cdot 10^9 = 2 \cdot 10^{14}. Πάντα long long.
  • Στο Subarray Divisibility το % της C++ δίνει αρνητικό υπόλοιπο για αρνητικό αριθμό· διόρθωσε με ((x % n) + n) % n.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το 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;
    }
};

Ελέγχθηκε σε 2.000 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.