Segment Tree

Τα Segment Trees είναι μια πολύ βασική δομή δεδομένων για τους διαγωνισμούς πληροφορικής. Μας βοηθούν να απαντήσουμε γρήγορα σε ερωτήματα πάνω σε διαστήματα (π.χ. άθροισμα σε πίνακα x των στοιχείων x[i]+x[i+1]+...+x[j]), ενώ επιτρέπουν δυναμικές αλλαγές (π.χ. αλλαγή της τιμή του x[i]). Τα Segment Trees είναι εύκολα στην υλοποίηση και αρκετά γρήγορα γιατί δεν απαιτούν τη χρήση pointers.

• Απλά Segment Trees
  • Εισαγωγικό πρόβλημα
  • Μια μικρή παραλλαγή
  • Ολοκληρώνοντας την λύση
  • Το Segment Tree ως δέντρο
  • Υλοποίηση
  • Τι πράξεις μπορούμε να κάνουμε;
    • Πράξεις με προσεταιριστική ιδιότητα
• Κόλπα
  • Αρχικοποίηση σε γραμμικό χρόνο
  • Συμπίεση
  • Lazy propagation
    • Εισαγωγικό πρόβλημα
    • Τεμπελιάζοντας
    • Διαχέοντας
• Προβλήματα για λύση
  • Συνήθη προβλήματα
  • Προβλήματα σε judge
• Πηγές

Απλά Segment Trees

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

Εισαγωγικό πρόβλημα

Εκφώνηση: Έχουμε έναν κενό πίνακα $N$ θέσεων, και ακολουθούν $Q$ ερωτήματα που ανήκουν σε μία από της εξής κατηγορίες:

• 0 pos val: Αύξηση της τιμής στην θέση pos του πίνακα κατά val.
• 1 from to: Άθροισμα των τιμών του πίνακα από τη θέση from έως τη θέση to.

Εάν απλά χρησιμοποιήσουμε έναν πίνακα, τότε η αύξηση τιμής είναι γρήγορη με πολυπλοκότητα $O(1)$. Το άθροισμα από την άλλη είναι αργό, με πολυπλοκότητα $O(N)$. Στη χειρότερη περίπτωση, η πολυπλοκότητα να απαντήσουμε σε όλα τα ερωτήματα είναι $O(Q\cdot 1 + Q\cdot N) = O(Q\cdot N)$.

int arr[MAXN];

void Update(int pos, int val) {
    arr[pos] += val;
}

int Query(int from, int to) {
    int out=0;
    for(int i = from; i <= to; ++i) {
        out += arr[i];
    }
    return out;
}

int main() {
    int N, Q;
    scanf("%d %d", &N, &Q);

    for(int i = 0; i < Q; ++i) {
        int op, a, b;
        scanf("%d %d %d", &op, &a, &b);
        if(op == 0) {
            Update(a, b);
        }
        else {
            printf("%d\n", Query(a, b));
        }
    }
}

Θα δούμε ότι με το Segment Tree, η πολυπλοκότητα της αύξησης τιμής θα ανέβει στο $O(\log N)$, ενώ η πολυπλοκότητα του αθροίσματος θα πέσει στο $O(\log N)$. Έτσι, η πολυπλοκότητα στη χειρότερη περίπτωση είναι $O(Q\cdot \log N)$.

Μια μικρή παραλλαγή

Έστω ότι γνωρίζουμε ότι τα ερωτήματα αθροισμάτων περιέχουν πάντα τρία στοιχεία, δηλαδή $to = from+2$. Προς το παρόν, η λύση μας κάνει μία πράξη στην αύξηση τιμής, και τρεις πράξεις στο άθροισμα. Μπορείτε να σκεφτείτε κάποιον τρόπο, κρατώντας αθροίσματα μερικών διαστημάτων, έτσι ώστε η αύξηση τιμής αλλά και το άθροισμα να γίνονται σε δύο πράξεις;

Η απάντηση δεν είναι προφανής, αλλά περιγράφεται σύντομα. Θα κρατήσουμε μη αλληλοκαλυπτόμενα αθροίσματα διαστημάτων δύο τιμών. Συγκεκριμένα, θα έχουμε έναν δεύτερο πίνακα, ο οποίος θα περιέχει τα αθροίσματα arr[0] + arr[1], arr[2] + arr[3], .... Κάθε φορά που ενημερώνουμε μια θέση στον πίνακα, θα ενημερώνουμε και μία θέση του δεύτερου πίνακα (καθώς τα διαστήματα είναι μη αλληλοκαλυπτόμενα). Κάθε φορά που ζητάμε ένα άθροισμα, μπορούμε να παρατηρήσουμε ότι κάθε διάστημα τριών στοιχείων θα περιέχει ένα από τα διαστήματα δύο τιμών του δεύτερου πίνακα, και το τρίτο στοιχείο θα το προσθέσουμε από τον αρχικό πίνακα.

int arr[MAXN], arr2[MAXN];

void Update(int pos, int val) {
    arr[pos] += val;
    arr2[pos/2] += val;
}

int Query(int from, int to) { 
    if(from%2 == 1) {
        return arr[from] + Query(from+1, to);    
    }
    if(to%2 == 0) {
        return Query(from, to-1) + arr[to];
    }
    int out = 0;
    for(int i = from/2; i <= to/2; ++i) {
        out += arr2[i];        
    }
    return out;
}

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

Ολοκληρώνοντας την λύση

Είδαμε λοιπόν ένα κόλπο που μπορεί να μειώσει το πλήθος των πράξεων για το άθροισμα στο μισό, αυξάνοντας κατά ένα το πλήθος των πράξεων για την αύξηση. Προσέξτε όμως τη χρήση του πίνακα arr2. Ο κώδικας μοιάζει αρκετά με την αρχική χρήση μας του πίνακα arr, μόνο που ο arr2 περιέχει τα μισά στοιχεία! Άρα, γιατί να μην χρησιμοποιήσουμε πάλι το ίδιο κόλπο έχοντας κάποιον πίνακα arr3;

Όμως και ο arr3 θα έχει την ίδια μορφή. Μπορούμε να συνεχίσουμε έτσι, αυξάνοντας το κόστος της αύξησης κατά ένα και μειώνοντας το κόστος του αθροίσματος στο μισό, μέχρι ο πίνακας να μην μειώνεται περαιτέρω (το οποίο συμβαίνει όταν περιέχει μόνο ένα στοιχείο). Δεν είναι δύσκολο να δούμε τώρα ότι η πολυπλοκότητα της αύξησης είναι ίση με $O(\log N)$ και του αθροίσματος με $O(\log N)$.

Παρόλο που έχουμε περιγράψει τον αλγόριθμο σε γενικές γραμμές, θα παρουσιάσουμε λίγες ακόμα ιδέες που διευκολύνουν την υλοποίηση.

Το Segment Tree ως δέντρο

Μπορεί να έχετε ήδη προσέξει ότι τα Segment Trees θυμίζουν ιδιαίτερα τα δέντρα δυαδικής αναζήτησης, μόνο που τα στοιχεία (οι θέσεις του πίνακα) βρίσκονται μόνο στα φύλλα. Πράγματι, μπορούμε να θεωρήσουμε τον κόμβο που περιέχει το άθροισμα όλων των στοιχείων ως την κορυφή, και για κάθε διάστημα, το πρώτο μισό αποτελεί το αριστερό του παιδί, ενώ το δεύτερο μισό αποτελεί το δεξί.

Άρα, το Segment Tree δεν είναι τίποτε άλλο από ένα πλήρες δυαδικό δέντρο. Έτσι, η τελική μας υλοποίηση θυμίζει αρκετά κάποιες ιδέες από την υλοποίηση δέντρων δυαδικής αναζήτησης, με τη διαφορά ότι η πληροφορία βρίσκεται πάντα στα φύλλα, και οι ενδιάμεσοι κόμβοι περιέχουν συμπληρωματικά δεδομένα. Μια βασική διαφορά του Segment Tree από τα γενικότερα δέντρα δυαδικής αναζήτησης είναι ότι μπορούμε να το υλοποιήσουμε χρησιμοποιώντας μόνο έναν πίνακα.

Υλοποίηση

Ανακεφαλαιώνοντας, διατηρούμε το άθροισμα κάθε διαστήματος με $2^k$ στοιχεία το οποίο ξεκινάει από πολλαπλάσιο του $2^k$, για κάθε $k$ από το μηδέν μέχρι το $\log N$.

Για κάθε διάστημα, τα δύο “παιδιά” του (αριστερό και δεξί) είναι το διάστημα που αντιστοιχεί στο πρώτο μισό, και το διάστημα που αντιστοιχεί στο άλλο μισό, τον οποίων το άθροισμα μας δίνει την τιμή του μεγαλύτερου. Επειδή θέλουμε να διευκολύνουμε την υλοποίηση, θα δώσουμε μια σειρά στα διαστήματα, έτσι ώστε το κάθε διάστημα να έχει μοναδική σειρά. Το διάστημα που καλύπτει όλον τον πίνακα έχει σειρά $1$. Επιπλέον, εάν κάποιο διάστημα έχει σειρά $i$, τότε το αριστερό του διάστημα θα έχει σειρά $2i$ και το δεξί θα έχει σειρά $2i+1$. Έτσι, χρειάζεται να χρησιμοποιήσουμε μόνο έναν πίνακα, έστω seg, για να αποθηκεύσουμε τις πληροφορίες των διαστημάτων, όπου το διάστημα με σειρά $i$ θα θα βρίσκεται στην θέση $i$ του seg. Δεν είναι δύσκολο να δούμε ότι ο πίνακας seg χρειάζεται το πολύ $4N$ θέσεις.

int seg[4*MAXN];

void Update(int pos, int val, int ind=1, int start=0, int end=MAXN) {
    if(start == end) {
        seg[ind] += val;
        return;
    }

    int mid = (start + end)/2;
    if(pos <= mid) {
        Update(pos, val, 2*ind, start, mid);
    }
    else {
        Update(pos, val, 2*ind+1, mid+1, end);
    }
    seg[ind] = seg[2*ind] + seg[2*ind+1];
}

int Query(int from, int to, int ind=1, int start=0, int end=MAXN) { 
    if(from == start && to == end) {
        return seg[ind];
    }

    int mid = (start + end)/2;
    if(to <= mid) {
        return Query(from, to, 2*ind, start, mid); 
    }
    else if(from > mid) {
        return Query(from, to, 2*ind+1, mid+1, end);
    }
    else {
        return Query(from, mid, 2*ind, start, mid) + Query(mid+1, to, 2*ind+1, mid+1, end);
    }
}

Τι πράξεις μπορούμε να κάνουμε;

Προς το παρόν είδαμε πώς να βρίσκουμε το άθροισμα διαστημάτων ενός πίνακα με το Segment Tree. Θα δούμε και άλλες “πράξεις” που μπορούμε να κάνουμε σε στοιχεία. Η πρόσθεση είναι μία πράξη πάνω σε αριθμούς, αλλά μπορούμε να κάνουμε πράξεις σε οτιδήποτε θέλουμε! Εκτός από πρόσθεση, τι άλλες πράξεις μπορούμε να κάνουμε;

Οποιαδήποτε πράξη έχει την προσεταιριστική ιδιότητα, μπορούμε να την χρησιμοποιήσουμε σε ένα Segment Tree.

Υπενθυμίζουμε ότι η προσεταιριστική ιδιότητα δηλώνει ότι η σειρά των πράξεων δεν έχει σημασία. Για παράδειγμα, στην πρόσθεση έχουμε $a+(b+c) = (a+b)+c$, ενώ στον πολλαπλασιασμό έχουμε $a\cdot(b\cdot c) = (a\cdot b)\cdot c$. Παρατηρήστε ότι δεν χρειαζόμαστε αντίστροφη πράξη (όπως η αφαίρεση), κάτι το οποίο είναι πολύ χρήσιμο.

Πράξεις με προσεταιριστική ιδιότητα

• Πρόσθεση/Πολλαπλασιασμός: $a+(b+c) = (a+b)+c = a+b+c$
  • π.χ. $1+(2+3) = 1+5 = 6 = 3+3 = (1+2)+3$
  • π.χ. $2\cdot (3\cdot 4) = 2\cdot 12 = 24 = 6\cdot 4 = (2\cdot 3)\cdot 4$
• Μέγιστο/Ελάχιστο: $\max(a,\max(b,c)) = \max(\max(a,b), c) = \max(a,b,c)$
  • π.χ. $\max(5, \max(1, 4)) = \max(5,4) = 5 = \max(5, 4) = \max(\max(5, 1), 4)$
  • π.χ. $\min(1,\min(2, 3)) = \min(1, 2) = 1 = \min(1, 3) = \min(\min(1, 2), 3)$
• ΜΚΔ/ΕΚΠ: $\gcd(a, \gcd(b,c)) = \gcd(\gcd(a,b), c) = \gcd(a,b,c)$
  • π.χ. $\gcd(10, \gcd(30, 6)) = \gcd(10, 6) = 2 = \gcd(10, 6) = \gcd(\gcd(10, 30), 6)$
  • π.χ. $\text{lcm}(10, \text{lcm}(30, 6)) = \text{lcm}(10, 30) = 30 = \text{lcm}(30, 6) = \text{lcm}(\text{lcm}(10, 30), 6)$
• Δυαδικές πράξεις (AND, OR, XOR): a & (b & c) = (a & b) & c = a & b & c
  • π.χ. 1101 & (1011 & 1100) = 1101 & 1000 = 1000 = 1001 & 1100 = (1101 & 1011) & 1100
  • π.χ. 1101 | (1011 | 1100) = 1101 | 1111 = 1111 = 1111 | 1100 = (1101 | 1011) | 1100
  • π.χ. 1101 ^ (1011 ^ 1100) = 1101 ^ 0111 = 1010 = 0110 ^ 1100 = (1101 ^ 1011) ^ 1100
• Συνδυασμός συνόλων/ταξινομημένων πινάκων: $a\cup(b\cup c) = (a\cup b) \cup c$
  • π.χ. $\{1, 3\} \cup (\{1, 2\} \cup\{4\}) = \{1, 3\}\cup \{1, 2,4\} = \{1,2,3,4\} = \{1,2,3\}\cup\{4\} = (\{1,3\}\cup\{1,2\})\cup \{4\}$
  • π.χ. $[1, 3] \cup ([1, 2] \cup[4]) = [1, 3]\cup [1, 2, 4] = [1,1,2,3,4] = [1,1,2,3]\cup[4] = ([1,3]\cup[1,2])\cup [4]$

Κόλπα

Υπάρχουν μερικές ιδέες που μπορούμε να εφαρμόσουμε στα Segment Trees έτσι ώστε να λύσουμε κάποια προβλήματα πιο εύκολα. Κάποιες (όπως το Lazy Propagation) είναι πιο χρήσιμες από άλλες, αλλά σε γενικές γραμμές καλό είναι να τις γνωρίζετε.

Αρχικοποίηση σε γραμμικό χρόνο

Έστω ότι στο εισαγωγικό πρόβλημα που περιγράψαμε παραπάνω, αντί ο αρχικός πίνακας να είναι άδειος, μας δινόταν η τιμή της κάθε θέσης. Αντί να καλέσουμε $Ν$ φορές την συνάρτηση Update (η οποία υπενθυμίζουμε ότι έχει πολυπλοκότητα $O(\log N)$), το οποίο θα έκανε την πολυπλοκότητα της αρχικοποίησης του πίνακα $O(N\log N)$, μπορούμε με μία αναδρομική συνάρτηση να αρχικοποιήσουμε όλες τις τιμές.

Η νέα μας συνάρτηση Build μοιάζει αρκετά με τις προηγούμενες. Όπως και πριν, χωρίζουμε το διάστημα που χτίζουμε στα δύο, και χτίζουμε αναδρομικά τα δύο διαστήματα έτσι ώστε να μπορούμε να συνδυάσουμε τις πληροφορίες τους στο μεγαλύτερο διάστημα.

int seg[4*MAXN], // Το Segment Tree
    inpt[MAXN];  // Ο αρχικός πίνακας

void Build(int ind=1, int start=0, int end=MAXN) {
    if(start == end) {
        seg[ind] = inpt[start];
        return;
    }
    
    int mid = (start+end)/2;
    Build(2*ind, start, mid);
    Build(2*ind+1, mid+1, end);
    
    seg[ind] = seg[2*ind] + seg[2*ind+1];
}

Συμπίεση

Όπως είδαμε πιο πάνω, η πολυπλοκότητα των συναρτήσεων Update και Query είναι λογαριθμική ως προς το $N$. Συνεπώς, το μέγεθος του πίνακα που αντικαθιστούμε με το Segment Tree δεν επηρεάζει πολύ την ταχύτητα του αλγορίθμου μας, παρά μόνο τη μνήμη που χρησιμοποιεί. Εάν γνωρίζουμε ότι το $N$ είναι τόσο μεγάλο ώστε το Segment Tree να υπερβαίνει την επιτρεπτή μνήμη, αλλά το $O(Q\log N)$ είναι εντός των χρονικών ορίων, αναγκαστικά έχουμε ότι το $Q$ είναι κατά πολύ μικρότερο του $N$, και άρα οι ενημερώσεις που θα γίνουν δεν αρκούν για να γεμίσουν μεγάλο μέρος του πίνακα. Άρα, το μεγαλύτερο μέρος του πίνακα (και άρα και του Segment Tree) θα είναι άδειο. Πώς μπορούμε να το εκμεταλλευτούμε αυτό για να μειώσουμε τη μνήμη που χρησιμοποιούμε;

Μπορούμε με έναν πολύ απλό τρόπο να συμπιέσουμε ένα Segment Tree χωρίς να αλλάξουμε σχεδόν καθόλου τον κώδικα! Η λύση είναι να αντικαταστήσουμε τον πίνακα που παραπάνω ονομάζουμε seg με ένα Hash Table, όπως το unordered_map της STL.

Μια εναλλακτική λύση για συμπίεση είναι η υλοποίηση του Segment Tree με τη χρήση pointers, το οποίο όμως θεωρούμε ότι κάνει την υλοποίηση πιο περίπλοκη, και δεν συμφέρει πλέον να χρησιμοποιούμε Segment Trees.

Να σημειωθεί ότι συνήθως σε περιπτώσεις όπου το εύρος τιμών υπερβαίνει κατά πολύ το πλήθος των εισαχθέντων τιμών (δηλαδή ο πίνακας είναι σχεδόν όλος άδειος), καταφεύγουμε σε άλλες δομές δεδομένων, κυρίως Binary Search Trees (για παράδειγμα Treaps), καθώς πετυχαίνουν καλύτερη πολυπλοκότητα και μεγαλύτερη ευελιξία.

Lazy propagation

Η λύση που παραθέσαμε στο εισαγωγικό πρόβλημα στην αρχή υποστηρίζει ενημερώσεις σε θέσεις του πίνακα και ερωτήματα σε διαστήματα. Με το Lazy Propagation, μπορούμε να κάνουμε και ενημερώσεις σε διαστήματα.

Εισαγωγικό πρόβλημα

Εκφώνηση: Έχουμε έναν κενό πίνακα $N$ θέσεων, και ακολουθούν $Q$ ερωτήματα που ανήκουν σε μία από της εξής κατηγορίες:

• 0 from to val: Αύξηση των τιμών του πίνακα από τη θέση from έως τη θέση to κατά val.
• 1 from to: Άθροισμα των τιμών του πίνακα από τη θέση from έως τη θέση to.

Με την αρχική μας λύση, στην χειρότερη περίπτωση, η πολυπλοκότητα να απαντήσουμε σε όλα τα ερωτήματα είναι $O(Q\cdot N\cdot \log N + Q\cdot \log N) = O(Q\cdot N\cdot \log N)$, καθώς για να κάνουμε αύξηση τιμών σε ένα εύρος πρέπει να αυξήσουμε κάθε τιμή ξεχωριστά. Ιδανικά, θα θέλαμε να επιταχύνουμε την αύξηση διαστήματος τιμών έτσι ώστε να επιστρέψουμε στο $O(Q\cdot \log N)$.

Η παρούσα λύση μας θα διανύσει το Segment Tree πολλές φορές για να ενημερώσει τα διαστήματα που επηρεάζονται. Όμως μπορούμε να παρατηρήσουμε ότι είναι πιθανό πολλά από τα επηρεαζόμενα διαστήματα να ταυτίζονται (ως άσκηση, βρείτε μία περίπτωση διαστήματος δύο τιμών που ταυτίζονται όλα τα διαστήματα εκτός από ένα, και μία περίπτωση που ταυτίζεται μόνο ένα). Μπορούμε λοιπόν να αλλάξουμε την συνάρτηση αύξησης, έτσι ώστε αντί να την καλούμε για κάθε στοιχείο του διαστήματος, μπορούμε να την καλούμε αναδρομικά, και να χωρίζουμε το διάστημα όπως κάνουμε για την συνάρτηση αθροίσματος.

void Update(int from, int to, int val, int ind=1, int start=0, int end=MAXN) {
    if(start == end) {
        seg[ind] += val;
        return;
    }

    int mid = (start + end)/2;
    if(to <= mid) {
        Update(from, to, val, 2*ind, start, mid);
    }
    else if(from > mid) {
        Update(from, to, val, 2*ind+1, mid+1, end);
    }
    else {
        Update(from, mid, val, 2*ind, start, mid);
        Update(mid+1, to, val, 2*ind+1, mid+1, end);
    }
    seg[ind] = seg[2*ind] + seg[2*ind+1];
}

Ποια είναι η πολυπλοκότητα της παραπάνω συνάρτησης; Εναλλακτικά, πόσες φορές θα κληθεί η αναδρομική συνάρτηση Update όταν θέλουμε να εκτελέσουμε μία αύξηση εύρους; Το βάθος της αναδρομής είναι ίσο με $\log N$, καθώς σε κάθε βήμα η τιμή του end-start μειώνεται στο μισό. Επιπλέον, σε κάθε αναδρομή, η συνάρτηση διακλαδίζεται το πολύ δύο φορές. Συνεπώς, η συνάρτηση Update καλείται το πολύ $2^{\log N} = N$ φορές. Έτσι, η πολυπλοκότητα της λύσης μας πέφτει στο $O(Q\cdot N)$.

Τεμπελιάζοντας

Ας εξετάσουμε μια ειδική περίπτωση αύξησης εύρους τιμών. Συγκεκριμένα, έστω ότι μας έρχεται ένα ερώτημα αύξησης όλων των τιμών του πίνακα κατά 1. Πώς επηρεάζονται τα μετέπειτα ερωτήματα;

Απλό! Κάθε ερώτημα αθροίσματος τιμών από τη θέση from έως τη θέση to θα έχει αύξηση της τιμής του κατά to-from+1. Συνεπώς, εάν έχουμε ένα τέτοιο ερώτημα, δεν είναι απαραίτητο να αλλάξουμε τον πίνακα, αλλά μπορούμε να αποθηκεύσουμε σε μια εξωτερική μεταβλητή (έστω lazy) την συνολική μεταβολή όλων των τιμών. Έτσι, κάθε φορά που λαμβάνουμε ερώτημα αθροίσματος, θα επιστρέφουμε την τιμή που μας δίνει η δομή μας, συν lazy*(to-from+1).

Γενικεύοντας την παραπάνω ιδέα, μπορούμε να έχουμε μία τιμή lazy για κάθε τιμή του seg, και για κάθε διάστημα που διανύουμε κατεβαίνοντας το Segment Tree, να λαμβάνουμε υπόψη την αντίστοιχη τιμή lazy.

int seg[4*MAXN], lazy[4*MAXN];

void Update(int from, int to, int val, int ind=1, int start=0, int end=MAXN) {
    if(start == from && end == to) {
        lazy[ind] += val;
        seg[ind] += val;
        return;
    }

    int mid = (start + end)/2;
    if(to <= mid) {
        Update(from, to, val, 2*ind, start, mid);
    }
    else if(from > mid) {
        Update(from, to, val, 2*ind+1, mid+1, end);
    }
    else {
        Update(from, mid, val, 2*ind, start, mid);
        Update(mid+1, to, val, 2*ind+1, mid+1, end);
    }
    seg[ind] = seg[2*ind] + seg[2*ind+1];
}

int Query(int from, int to, int ind=1, int start=0, int end=MAXN) { 
    if(from == start && to == end) {
        return seg[ind];
    }

    int mid = (start + end)/2;
    if(to <= mid) {
        return Query(from, to, 2*ind, start, mid) + (to-from+1)*lazy[ind]; 
    }
    else if(from > mid) {
        return Query(from, to, 2*ind+1, mid+1, end) + (to-from+1)*lazy[ind];
    }
    else {
        return Query(from, mid, 2*ind, start, mid) + Query(mid+1, to, 2*ind+1, mid+1, end) + (to-from+1)*lazy[ind];
    }
}

Δεν είναι ιδιαίτερα δύσκολο να δείξουμε αυτή τη φορά ότι η πολυπλοκότητα είναι και πάλι $O(Q\log N)$!

Διαχέοντας

Δυστυχώς, η περιγραφή του Lazy propagation δεν τελειώνει εδώ. Η λύση που παραθέσαμε παραπάνω εκμεταλλεύεται την μεταβατική ιδιότητα του αθροίσματος. Για πιο πολύπλοκα προβλήματα, όμως, χρειαζόμαστε μια μικρή μετατροπή που κάνει τη λύση πιο γενική. Συγκεκριμένα, θα θέλαμε να αφαιρέσουμε τον υπολογισμό + (to-from+1)*lazy[ind] από τη συνάρτηση Query.

Ευτυχώς, η αλλαγή που χρειαζόμαστε είναι μικρή. Αντί να συνυπολογίζουμε την τιμή του lazy κατά τη διάρκεια του Query, μπορούμε απλά να την “διαχέουμε” στο αριστερό και το δεξί διάστημα με τη συνάρτηση Propagate.

void Propagate(start, end, ind) {
    if(lazy[ind] == 0) {
        return;
    }

    int mid=(start+end)/2;
    Update(start, mid, lazy[ind], 2*ind, start, mid);
    Update(mid+1, to, lazy[ind], 2*ind+1, mid+1, end);
    lazy[ind] = 0;
}

int Query(int from, int to, int ind=1, int start=0, int end=MAXN) { 
    if(from==start && to==end) {
        return seg[ind];
    }

    Propagate(start, end, ind);

    int mid = (start + end)/2;
    if(to <= mid) {
        return Query(from, to, 2*ind, start, mid); 
    }
    else if(from > mid) {
        return Query(from, to, 2*ind+1, mid+1, end);
    }
    else {
        return Query(from, mid, 2*ind, start, mid) + Query(mid+1, to, 2*ind+1, mid+1, end);
    }
}

Προβλήματα για λύση

Συνήθη προβλήματα

Εκφώνηση: Δίνεται ένας πίνακας $N$ στοιχείων, και θα γίνουν $Q$ ερωτήματα. Στην πρώτη γραμμή δίνονται $N$ αριθμοί: τα στοιχεία του πίνακα. Ακολουθούν $Q$ γραμμές, της μορφής:

• U i j v: Προσθέτουμε v σε όλες τις θέσεις του πίνακα από i έως j.
• Q i j: Επιστρέφουμε το μέγιστο στοιχείο του πίνακα από τη θέση i έως τη θέση j, και το πλήθος φορών που εμφανίζεται.

Πολυπλοκότητα: $O(N + Q\log N)$.

Εκφώνηση: Δίνεται ένας πίνακας $N$ μη αρνητικών στοιχείων, και θα γίνουν $Q$ ερωτήματα. Στην πρώτη γραμμή δίνονται $N$ αριθμοί: τα στοιχεία του πίνακα. Ακολουθούν $Q$ γραμμές, της μορφής:

• U i v: Αλλάζουμε την τιμή της θέσης i σε v. To v είναι πάντα μη αρνητικό.
• Q v: Επιστρέφουμε την ελάχιστη θέση i έτσι ώστε το ελάχιστο κοινό πολλαπλάσιο των στοιχείων μέχρι θέση αυτή να είναι τουλάχιστον v.

Πολυπλοκότητα: $O(N + Q\log N)$.

Hint: Αν κάνετε binary search θα έχετε πολυπλοκότητα $O(N + Q\log^2N)$. Σκεφτείτε τι επιπλέον πράξεις κάνετε, και πώς μπορείτε να αλλάξετε την συνάρτηση Query.

Εκφώνηση: Δίνεται ένας πίνακας $N$ στοιχείων, και θα γίνουν $Q$ ερωτήματα. Στην πρώτη γραμμή δίνονται $N$ αριθμοί: τα στοιχεία του πίνακα. Ακολουθούν $Q$ γραμμές, της μορφής:

• U i v: Αλλάζουμε την τιμή της θέσης i σε v.
• Q i j: Να βρεθεί το μέγιστο άθροισμα συνεχόμενου διαστήματος εντός του i..j.

Πολυπλοκότητα: $O(N+Q\log N)$.

Hint: Πρέπει να κρατήσετε επιπλέον πληροφορίες εκτός από το μέγιστο άθροισμα συνεχόμενου διαστήματος, καθώς η πράξη αυτή δεν έχει προσεταιριστική ιδιότητα. Θα χρειαστείτε επιπλέον τρεις τιμές.

Εκφώνηση: Δίνεται ένας πίνακας $N$ στοιχείων, και θα γίνουν $Q$ ερωτήματα. Στην πρώτη γραμμή δίνονται $N$ αριθμοί: τα στοιχεία του πίνακα. Ακολουθούν $Q$ γραμμές, της μορφής:

• U i v: Αλλάζουμε την τιμή της θέσης i σε v.
• Q i j v: Να βρεθεί εάν υπάρχει η τιμή v εντός του διαστήματος i..j.

Πολυπλοκότητα: $O(N + Q\log^2 N)$.

Hint: Θα χρησιμοποιήσετε $O(N\log N)$ χώρο. Δείτε τις πράξεις με προσεταιριστική ιδιότητα.

Προβλήματα σε judge

Codeforces: Sereja and Brackets

Codeforces: Ant colony

Codeforces: Circular RMQ

Codeforces: A Simple Task

Codeforces: The Child and Sequence

Codeforces: Alphabet Permutations

SpOJ: K-th Number

SpOJ: The day of the competitors

SpOJ: D-query

SpOJ: Snow White and the N dwarfs

Πηγές

e-maxx.ru: Segment Trees (μέσω Google Translate)

Codeforces: Segment Tree Problems

Wikipedia: Associative property

Σχόλια