Binary Indexed Tree

Το Binary Indexed Tree (BIT) είναι μια ιδιαίτερα χρήσιμη και εύκολη δομή δεδομένων για διαγωνισμούς πληροφορικής. Τα κύρια πλεονεκτήματα του είναι ότι χρειάζεται μικρό ποσό κώδικα (περίπου 10 γραμμές) και για τη χρήση του είναι πάρα πολύ αποδοτικό (έχει μικρό σταθερό παράγοντα στη πολυπλοκότητά του σε σύγκριση με άλλες δομές που επιτελούν παρόμοιες λειτουργίες) επειδή χρησιμοποιεί πράξεις με bitwise operators που είναι πάρα πολύ γρήγορες. Αρχικά θα παρουσιάσουμε το πρόβλημα των ερωτημάτων αθροίσματος σε διαστήματα καθώς και διάφορες τεχνικές για να το λύσουμε και στη συνέχεια θα δούμε πως μπορεί να λυθεί με BIT.

Εισαγωγή στα bitwise operators
Range Sum Queries
Range updates και point queries
Prefix min/max queries και point updates
Γενίκευση στις ν διαστάσεις
Προβλήματα
Πηγές

Εισαγωγή στα bitwise operators

Πριν ξεκινήσουμε, ακολουθεί μια πολύ σύντομη εισαγωγή στις χρήσιμες πράξεις με bitwise operators. Αν είσαστε εξοικειωμένοι με αυτά, μπορείτε να προχωρήσετε στην παράγραφο που ορίζει το lsone.

Τα bitwise operators είναι τελεστές που εκτελούν πράξεις στην δυαδική αναπαράσταση ακεραίων (και όχι στην δεκαδική όπως πχ. η πρόσθεση και η αφαίρεση). Οι πιο βασικοί είναι: NOT, OR, AND, XOR, SHIFT LEFT, SHIFT RIGHT οι οποίοι στην C++ και τις περισσότερες γλώσσες προγραμματισμού συμβολίζονται αντίστοιχα ~, |, &, ^, <<, >>.

Το ~ αντιστρέφει κάθε bit (μην μπερδέψετε αυτό το bit με το θέμα του άρθρου!) στην δυαδική αναπαράσταση του αριθμού στον οποίο εφαρμόζεται. Έτσι, το ~ $101$ γίνεται $010$ . Δοκιμάστε x = ~5; στην C++.

Για όλες τις υπόλοιπες πράξεις θα χρειαστούν δύο αριθμοί $a$ , $b$ .

Το αποτέλεσμα στο | έχει κάποιο bit του ίσο με 0 μόνο και τα δύο αντίστοιχα bits των αριθμών είναι ίσα με 0, διαφορετικά είναι ίσο με 1. Για παράδειγμα, το $100$ | $110$ ισούται με $110$ . Μπορείτε να δοκιμάσετε x = 4 | 6;.
Με όμοιο τρόπο, το & επιστρέφει 1 μόνο αν και τα δύο αντίστοιχα bits είναι ίσα με 1.
Το ^ επιστρέφει 1 μόνο αν τα δύο αντίστοιχα bits είναι διαφορετικά μεταξύ τους, δηλαδή το ένα ισούται με 0 και το άλλο με 1.
Το << μετατοπίζει όλα τα bits του πρώτου αριθμού όσες θέσεις αριστερά λέει ο δεύτερος και εισάγει μηδενικά στα δεξιά. Για παράδειγμα, το $101$ << $2$ θα γίνει $10100$ . Δοκιμάστε x = 5 << 2;.
Το >> κάνει την ίδια δουλειά με το << αλλά αντίστροφα, δηλαδή μετατοπίζει τα bits προς τα δεξιά. Έτσι το $101$ >> $2$ θα γίνει $001$ .

Προσοχή!: Τα bitwise operators μπορεί να προκαλέσουν πολύ περίεργα λάθη αν δεν χρησιμοποιηθούν σωστά λόγω της σειράς εκτέλεσης των πράξεων. Για αυτόν τον λόγο προτείνεται να βάζετε πάντα παρενθέσεις γύρω από τις παραστάσεις που τα περιλαμβάνουν.

Μία πράξη που θα χρειαστούμε πολύ στο BIT είναι αυτή που παίρνει ως input έναν αριθμό $x$ και μας επιστρέφει έναν άλλο αριθμό ο οποίος περιέχει μόνο το least significant set bit (οπότε αυτή η πράξη ορίζεται μόνο για αριθμούς που έχουν τουλάχιστον ένα bit ίσο με 1 που είναι όλοι εκτός του 0). Αυτό είναι ουσιαστικά το πρώτο bit που θα συναντήσουμε από τα δεξιά στη δυαδική αναπαράσταση του $x$ το οποίο ισούται με 1. Θα ονομάσουμε αυτή τη πράξη lsone(x) (από το least significant one).

Θα ήταν καλό να προσπαθήσετε να σκεφτείτε μόνοι σας πως να φτιάξετε το lsone με κάποιον συνδυασμό των πράξεων που ήδη ξέρετε (όχι μόνο bitwise) πριν δείτε την απάντηση.

Αρχικά ας δούμε τι κάνει η αφαίρεση στην δυαδική αναπαράσταση ενός αριθμού. Όταν αφαιρέσουμε το 1 από το $..100...0$ τότε το αποτέλεσμα που παίρνουμε είναι το $..011...1$ . Αυτό σημαίνει ότι αλλάζουμε το least significant set bit από 1 σε 0 και όλα τα δεξιά του από 0 σε 1. Μετά από αυτό, μια εύκολη λύση θα ήταν να ορίσουμε τη πράξη μας ως εξής (παρατηρήστε πόσο συχνά χρησιμοποιούμε παρενθέσεις):

#define lsone(x) (x - (x & (x - 1)))

Ουσιαστικά, αφού όλα τα bits αριστερά του most significant set bit είναι ίδια στο x και το (x - 1) ενώ όλα τα υπόλοιπα ίδια το AND θα μας επιστρέψει τον αριθμό x χωρίς το bit που μας ενδιαφέρει (θα είναι μόνο αυτό που έχει αφαιρεθεί). Έτσι αρκεί να πάρουμε την διαφορά του x και του αποτελέσματος αυτού για να βρούμε το ζητούμενο. Από εδώ και στο εξής όπου γράφουμε lsone θα αναφερόμαστε σε αυτή τη παράσταση.

Έναν άλλο τρόπο που χρησιμοποιούμε συχνά, ο οποίος είναι ευκολότερο να γραφτεί είναι ο

#define lsone(x) (x & (-x))

αλλά δεν θα τον περιγράψουμε περαιτέρω.

Range Sum Queries

Δίνεται ένας πίνακας $A$ μεγέθους $N$ με ακέραιους αριθμούς και δύο είδη ερωτημάτων:

query(l, r): Ποιο είναι το άθροισμα των αριθμών του πίνακα στο $[l, r]$ ;

update(p, v): Πρόσθεσε v στη θέση p

Παρακάτω παρουσιάζουμε μερικούς από τους τρόπους για να λύσουμε αυτό το πρόβλημα. Προτείνουμε όμως να σκεφτείτε εσείς κάποιες λύσεις προτού προχωρήσετε!

Naive Solution: $O(N)$ ανά query και $O(1)$ ανά update

Αυτή είναι η ευκολότερη λύση αφού απλά εξομοιώνουμε τα operations όπως ορίστηκαν. Με αυτόν τον τρόπο, στη χειρότερη περίπτωση το query θα έχει $O(N)$ πολυπλοκότητα και το update θα έχει $O(1)$ .

Partial sums: $O(1)$ ανά query και $O(N)$ ανά update

Ας κατασκευάσουμε τα μερικά αθροίσματα (partial sums ή prefix sums) πάνω στον πίνακα $A$ . Δημιουργούμε λοιπόν έναν νέο πίνακα $S$ έτσι ώστε $S_1 = A_1$ και $S_i = S_{i-1} + A_i$ . (Παρατήρηση: ένα συχνό μικρό κολπάκι είναι να χρησιμοποιούμε αρίθμηση θέσεων ξεκινώντας από το 1 και όχι από το 0 έτσι ώστε να μην χρειάζεται να ελέγχουμε οριακές περιπτώσεις!)

Έτσι, το query θα γίνεται σε $O(1)$ αφού το άθροισμα από το $l$ έως το $r$ θα μπορούμε να το παίρνουμε αμέσως ως $S_r - S_{l-1}$ . Στο update όμως, ούτως ώστε να διατηρήσουμε τα μερικά αθροίσματα όταν αλλάξουμε το $A_i$ (και συνεπώς το $S_i$ ) κατά $+v$ θα χρειαστεί να αλλάξουμε και όλα τα $S_j$ με $i < j \leq N$ κατά $+v$ . Άρα η πολυπλοκότητα είναι (στη χειρότερη περίπτωση) ίση με $O(N)$ ανά update.

Binary Indexed Tree: $O(\log N)$ ανά query και update

Το BIT μπορεί να λύσει το πρόβλημα σε $O(\log N)$ ανά query και update με μία προ-επεξεργασία σε $O(N\log N)$ . Πως όμως δουλεύει αυτή η δομή;

Αρχικά δημιουργούμε έναν πίνακα bit του οποίου η κάθε θέση θα περιλαμβάνει το άθροισμα περισσότερων από μιας θέσης του $A$ . Το μυστικό βρίσκεται στο ότι επιλέγουμε βέλτιστα ποιο σύνολο αριθμών αντιστοιχίζεται σε κάθε θέση του πίνακα αυτού. Συγκεκριμένα, το bit[i] θα περιλαμβάνει το άθροισμα αριθμών στο διάστημα $(i - lsone(i), i]$ . Τώρα, θα δούμε γιατί ένας τέτοιος διαχωρισμός είναι ιδιαίτερα χρήσιμος.

Μπορούμε να φτιάξουμε μια συνάρτηση ask(p) που να επιστρέφει το άθροισμα όλων των στοιχείων του $A$ από το $1$ έως το $p$ . Αν έχουμε αυτή τη συνάρτηση στη διάθεσή μας μπορούμε εύκολα να απαντήσουμε στο query(l, r) ως ask(r) - ask(l - 1). Με βάση τον ορισμό που έχουμε δώσει για το bit[i] το ask θα χρειάζεται να αθροίζει τα bit[p] + bit[p - lsone(p)] + bit[p - lsone(lsone(p))] ... μέχρι το p να μηδενιστεί. Έτσι θα έχουμε αθροίσει όλους τους αριθμούς σε συνεχή διαστήματα που περιλαμβάνουν το διάστημα που μας ενδιαφέρει $[1, p]$ . Αφού κάθε φορά αφαιρούμε ένα bit από τον αριθμό $p$ , στην χειρότερη περίπτωση θα αφαιρέσουμε $O(\log N)$ bits, από όπου προκύπτει και η πολυπλοκότητα. Ο κώδικας είναι:

int ask(int p) {
    int res = 0;
    for (; p > 0; p -= lsone(p))
        res += bit[p];
    return res;
}

Όσον αφορά το update(p, v), με τον τρόπο που ορίσαμε το bit[i], για να περιέχει μια θέση $j$ την αναβάθμιση που μόλις κάναμε στη θέση $p$ θα πρέπει το least significant set bit του $j$ να βρίσκεται αριστερά από του $p$ (ή να είναι το ίδιο το $p$ ). Επιπλέον, δεν πρέπει να αλλάξουμε τα σημαντικότερα ψηφία αριστερά αυτού του $j$ στο $p$ γιατί έτσι το αντίστοιχο διάστημα δεν θα περιέχει στο άθροισμά του τον αριθμό $p$ . Ο κώδικας είναι:

void update(int p, int v) {
    for (; p <= N; p += lsone(p))
        bit[p] += v;
}

Το αρχικό preprocessing σε $O(\log N)$ που ισχυριστήκαμε ότι χρειάζεται είναι για να εισάγουμε τα $N$ στοιχεία του πίνακά μας στην δομή δεδομένων. Αυτό γίνεται απλά αν σε ένα bit που αρχικά περιέχει μόνο μηδενικά κάνουμε update για ένα ένα τα στοιχεία.

void build() {
    for (int i = 1; i <= N; i++)
        update(i, A[i]);
}

Άλλες πράξεις που μπορούν να γίνουν με ένα Binary Indexed Tree είναι για παράδειγμα ο πολλαπλασιασμός και το bitwise xor.

Range updates και point queries

Μέχρι στιγμής αναφέρθηκε το πως αντιμετωπίζουμε point updates και range queries, δηλαδή updates σε σημεία και queries σε διαστήματα. Μπορούμε όμως εύκολα με την ίδια υλοποίηση και μικρή διαφορά στην λογική να κάνουμε και το αντίστροφο, δηλαδή updates σε διαστήματα και queries σε σημεία.

Ξανά, προτείνουμε να προσπαθήσετε να σκεφτείτε μόνοι σας έναν τρόπο να λύσετε αυτό το πρόβλημα χρησιμοποιώντας μόνο τα operations που έχετε μάθει.

Η λύση είναι να παίρνουμε κάθε φορά το άθροισμα όλων των αριθμών από την αρχή έως την ζητούμενη θέση (δηλαδή θα κάνουμε ένα απλό query) όμως να μεταχειριζόμαστε διαφορετικά τα updates. Για ένα update από το $i$ έως το $j$ με τιμή $v$ μπορούμε να προσθέσουμε $+v$ στη θέση $i$ και $-v$ στη θέση $j + 1$ . Έτσι, αν η θέση ενδιαφέροντος βρίσκεται πριν το $i$ δεν επηρεάζεται καθόλου, αν βρίσκεται μετά το $j$ πάλι δεν επηρεάζεται καθόλου επειδή συνολικά έχει προστεθεί μία φορά το $v$ και έχει επίσης αφαιρεθεί μία φορά και αν βρίσκεται στο $[i, j]$ τότε η τιμή της θα ανέβει κατά $v$ επειδή η μόνη αναβάθμιση που θα συμβάλει στο άθροισμα είναι η πρώτη στην οποία προσθέτουμε $+v$ στο $i$ .

Prefix min/max queries και point updates

Με τον ίδιο τρόπο που μπορούμε να κάνουμε queries αθροίσματος μπορούμε να αντιμετωπίζουμε και queries ελάχιστου ή μέγιστου αλλά μόνο σε προθέματα (prefixes) του πίνακά μας. Αυτό συμβαίνει επειδή το minimum και το maximum δεν έχουν αντίστροφες πράξεις (όπως πχ έχει η πρόσθεση την αφαίρεση) και συνεπώς δεν μπορούμε να συνθέσουμε την απάντηση σε οποιοδήποτε διάστημα $[i, j]$ γνωρίζοντας μόνο το ελάχιστο (ή το μέγιστο) στα $[1, i - 1]$ και $[1, j]$ . Με τον ίδιο τρόπο γίνεται να αντιμετωπίσουμε queries και updates με οποιαδήποτε άλλη πράξη που δεν έχει αντίστροφη πράξη (όπως πχ. ο ΜΚΔ ή το ΕΚΠ). Ακολουθεί παράδειγμα με την πράξη του max:

#define lsone(x) (x & (-x))

int bit[MAXN], N;

int query(int p) {
    int res = -INF;
    while (p > 0) {
        res = max(res, bit[p]);
        p -= lsone(p);
    }
    return res;
}

void update(int p, int val) {
    while (p <= N) {
        bit[p] = max(bit[p], val);
        p += lsone(p);
    }
}

Γενίκευση στις ν διαστάσεις

Ένα ακόμη πλεονέκτημα της δομής αυτής είναι ότι μπορεί πανεύκολα να γενικευτεί για πολλές διαστάσεις. Το μόνο που έχετε να κάνετε είναι να βάλετε ένα δεύτερο BIT σε κάθε θέση του πρώτου και ένα τρίτο σε κάθε θέση του δεύτερου κ.ο.κ. Ακολουθεί παράδειγμα για τις δύο διαστάσεις:

#define lsone(x) (x & (-x))

int bit[MAXN][MAXN], N;

int ask(int x0, int y0) {
    int res = 0;
    for (int x = x0; x > 0; x -= lsone(x))
        for (int y = y0; y > 0; y -= lsone(y))
            res += bit[x][y];
    return res;
}

void add(int x0, int y0, int v) {
    for (int x = x0; x <= N; x += lsone(x))
        for (int y = y0; y <= N; y += lsone(y))
            bit[x][y] += v;
}

Προβλήματα

Πηγές

A New Data Structure for Cumulative Frequency Tables [PDF]