Ένα δέντρο τμήματος και ένα δέντρο Fenwick (Binary Indexed Tree, BIT) απαντούν τόσο σε ερωτήματα εύρους (π.χ. άθροισμα πάνω από [l, r]) όσο και σε ενημερώσεις σημείου σε O(log n), σε σύγκριση με O(n) για σάρωση αφελή ή ενημερώσεις O(n) για πίνακα προθέματος-αθροίσματος.
Array + many "sum of range [l,r]" and "update index i" calls:
naive prefix sums: query O(1) but UPDATE is O(n)
segment/Fenwick: query O(log n) AND update O(log n)
class Fenwick:
def __init__(self, n):
self.t = [0]*(n+1)
def update(self, i, delta): # O(log n)
i += 1
while i < len(self.t):
self.t[i] += delta
i += i & (-i) # jump to next responsible node
def prefix(self, i): # sum of [0..i], O(log n)
i += 1; s = 0
while i > 0:
s += self.t[i]
i -= i & (-i)
return s
def range_sum(self, l, r):
return self.prefix(r) - self.prefix(l-1)
Ένα δέντρο τμήματος αποθηκεύει ένα συγκεντρωτικό για κάθε τμήμα πίνακα σε ένα δυαδικό δέντρο, υποστηρίζοντας οποιαδήποτε συσχετιστική λειτουργία (άθροισμα, ελάχιστο, μέγιστο, gcd) και με laze propagation και ενημερώσεις εύρους.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Δέντρο τμήματος | |
|---|---|---|
| Ερώτημα / ενημέρωση | O(log n) | O(log n) |
| Χώρος | O(n) | O(2n) |
| Λειτουργίες | αθροίσματα (αντιστρέψιμα) | οποιαδήποτε συσχετιστική λειτ |
| Ενημερώσεις εύρους | δυσκολότερο | εύκολο (laze propagation) |
| Μέγεθος κώδικα | ελάχιστο | μεγαλύτερο |
Αυτές οι δομές κάνουν "ενημερώστε μια τιμή, στη συνέχεια ρωτήστε ένα συγκεντρωτικό πάνω από ένα εύρος" γρήγορα — απαραίτητο για ανταγωνιστικό προγραμματισμό, παράθυρα ανάλυσης και προβλήματα διαστήματος.
Η επιλογή μεταξύ τους είναι ένα εμπόριο: ένα δέντρο Fenwick είναι μικρό και γρήγορο για αθροίσματα, ενώ ένα δέντρο τμήματος είναι πιο ευέλικτο για φορτία εργασίας min/max/ενημερώσεων εύρους.