uniolympiads English

Δέντρο Fenwick

Αλλαγή ενός στοιχείου και άθροισμα προθέματος, και τα δύο σε O(log⁡n)O(\log n), με έναν πίνακα και δύο βρόχους.

Πότε

Όταν τα αθροίσματα προθεμάτων δεν αρκούν επειδή ο πίνακας αλλάζει ανάμεσα στα ερωτήματα. Για αθροίσματα (ή οτιδήποτε έχει αντίστροφο, όπως το xor) είναι πιο σύντομο και πιο γρήγορο από ένα segment tree.

Η ιδέα

Με αρίθμηση από το 1, ο κόμβος ii κρατά το άθροισμα των τελευταίων i&(−i)i \mathbin{\&} (-i) στοιχείων μέχρι και το ii. Το i&(−i)i \mathbin{\&} (-i) είναι το χαμηλότερο bit του ii που είναι 1. Για παράδειγμα, ο κόμβος 12=1100212 = 1100_2 κρατά τα a9,…,a12a_9, \dots, a_{12}.

  • Πρόθεμα ως το ii: προσθέτεις το tit_i και σβήνεις το χαμηλότερο bit, i−=i&(−i)i \mathrel{-}= i \mathbin{\&} (-i), μέχρι το 0.
  • Αλλαγή στο ii: ενημερώνεις το tit_i και ανεβαίνεις, i+=i&(−i)i \mathrel{+}= i \mathbin{\&} (-i), μέχρι το nn.

Κάθε βρόχος κάνει το πολύ ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 βήματα.

Ενημέρωση διαστήματος, ερώτημα σημείου. Το Range Update Queries θέλει «πρόσθεσε vv στο [l,r][l, r]» και «πόσο είναι το aka_k;». Κράτα τον πίνακα διαφορών μέσα στο Fenwick: add(l, v), add(r + 1, -v), και το aka_k είναι το prefix(k).

Το kk-οστό στοιχείο. Με μη αρνητικές τιμές, το lowerBound(k) κατεβαίνει στα bits από το μεγαλύτερο και βρίσκει το μικρότερο ii με πρόθεμα ≥k\ge k, σε O(log⁡n)O(\log n). Με μετρητές εμφάνισης, αυτό είναι το kk-οστό μικρότερο στοιχείο ενός πολυσυνόλου.

Παγίδες

  • Η αρίθμηση είναι από το 1. Με add(0, v) ο βρόχος δεν τελειώνει ποτέ, γιατί 0&0=00 \mathbin{\&} 0 = 0.
  • Στο Salary Queries οι τιμές φτάνουν το 10910^9. Συμπίεσε τις συντεταγμένες πρώτα, διαβάζοντας όλα τα ερωτήματα offline.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/fenwick.cpp
// 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

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

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

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