Δέντρο Fenwick
Αλλαγή ενός στοιχείου και άθροισμα προθέματος, και τα δύο σε , με έναν πίνακα και δύο βρόχους.
Πότε
Όταν τα αθροίσματα προθεμάτων δεν αρκούν επειδή ο πίνακας αλλάζει ανάμεσα στα ερωτήματα. Για αθροίσματα (ή οτιδήποτε έχει αντίστροφο, όπως το xor) είναι πιο σύντομο και πιο γρήγορο από ένα segment tree.
Η ιδέα
Με αρίθμηση από το 1, ο κόμβος κρατά το άθροισμα των τελευταίων στοιχείων μέχρι και το . Το είναι το χαμηλότερο bit του που είναι 1. Για παράδειγμα, ο κόμβος κρατά τα .
- Πρόθεμα ως το : προσθέτεις το και σβήνεις το χαμηλότερο bit, , μέχρι το 0.
- Αλλαγή στο : ενημερώνεις το και ανεβαίνεις, , μέχρι το .
Κάθε βρόχος κάνει το πολύ βήματα.
Ενημέρωση διαστήματος, ερώτημα σημείου. Το Range Update Queries θέλει «πρόσθεσε στο » και «πόσο είναι το ;». Κράτα τον πίνακα διαφορών μέσα στο Fenwick: add(l, v), add(r + 1, -v), και το είναι το prefix(k).
Το -οστό στοιχείο. Με μη αρνητικές τιμές, το lowerBound(k) κατεβαίνει στα bits από το μεγαλύτερο και βρίσκει το μικρότερο με πρόθεμα , σε . Με μετρητές εμφάνισης, αυτό είναι το -οστό μικρότερο στοιχείο ενός πολυσυνόλου.
Παγίδες
- Η αρίθμηση είναι από το 1. Με
add(0, v)ο βρόχος δεν τελειώνει ποτέ, γιατί . - Στο
Salary Queriesοι τιμές φτάνουν το . Συμπίεσε τις συντεταγμένες πρώτα, διαβάζοντας όλα τα ερωτήματα offline.
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// Fenwick tree (binary indexed tree), 1-indexed.
// add(i, v): a[i] += v. prefix(i): a[1] + ... + a[i]. Both O(log n).
// i & -i is the lowest set bit of i: node i stores the sum of the last (i & -i) elements up to i.
struct Fenwick {
int n;
vector<ll> tree;
Fenwick(int size) : n(size), tree(size + 1, 0) {}
void add(int i, ll v) {
while (i <= n) {
tree[i] += v;
i += i & -i;
}
}
ll prefix(int i) {
ll s = 0;
while (i > 0) {
s += tree[i];
i -= i & -i;
}
return s;
}
ll rangeSum(int l, int r) {
return prefix(r) - prefix(l - 1);
}
// Smallest i with prefix(i) >= k, assuming all values are non-negative. Returns n + 1 if none.
int lowerBound(ll k) {
int pos = 0;
int step = 1;
while (step * 2 <= n) {
step *= 2;
}
while (step > 0) {
if (pos + step <= n && tree[pos + step] < k) {
pos += step;
k -= tree[pos];
}
step /= 2;
}
return pos + 1;
}
};
Ελέγχθηκε σε 500 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Για εξάσκηση στο CSES
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Dynamic Range Sum Queries · Range Queries
- Range Update Queries · Range Queries
- Salary Queries · Range Queries
Περισσότερα στο USACO Guide
- Point Update Range Sum · usaco.guide/gold/PURS
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.