Αθροίσματα προθεμάτων
Άθροισμα οποιουδήποτε διαστήματος σε , μετά από ένα πέρασμα . Και το αντίστροφο: πολλές προσθέσεις σε διαστήματα με τον πίνακα διαφορών.
Πότε
Ο πίνακας δεν αλλάζει και έρχονται πολλά ερωτήματα «άθροισμα από ως ». Με το δεν περνά, το περνά άνετα.
Η ιδέα
Ορίζουμε και . Τότε
Η μετατόπιση κατά ένα, με μήκους , γλιτώνει την ειδική περίπτωση .
Σε δύο διαστάσεις ισχύει το ίδιο με εγκλεισμό–αποκλεισμό: το ορθογώνιο είναι το μεγάλο ορθογώνιο από την αρχή, μείον δύο λωρίδες, συν τη γωνία που αφαιρέθηκε δύο φορές.
Πίνακας διαφορών. Είναι η αντίστροφη πράξη. Για να προσθέσεις σε όλο το , γράφεις και . Στο τέλος τα αθροίσματα προθεμάτων του δίνουν τον πίνακα.
Η κίνηση που ξεκλειδώνει προβλήματα
«Πόσα διαστήματα έχουν άθροισμα ;» Ένα διάστημα έχει άθροισμα αν και μόνο αν . Περνάς τα με τη σειρά και μετράς σε ένα map πόσες φορές έχεις ήδη δει το . Το ίδιο, με υπόλοιπα, λύνει το «άθροισμα διαιρετό με ».
Παγίδες
- Τα αθροίσματα ξεπερνούν το
int: . Πάνταlong long. - Στο
Subarray Divisibilityτο%της C++ δίνει αρνητικό υπόλοιπο για αρνητικό αριθμό· διόρθωσε με((x % n) + n) % n.
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// 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
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Static Range Sum Queries · Range Queries
- Forest Queries · Range Queries
- Subarray Sums II · Sorting and Searching
- Subarray Divisibility · Sorting and Searching
Περισσότερα στο USACO Guide
- Introduction to Prefix Sums · usaco.guide/silver/prefix-sums
- More on Prefix Sums · usaco.guide/silver/more-prefix-sums
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.