Massiv verilib: a[l:r] aralığının cəmini cavablandırmalı və ayrı-ayrı elementləri a[i] = v dəyişməliyik. Hər ikisindən yüz minlərlə olanda nə naiv dövr (sorğu başına O(n)), nə də prefiks cəmləri (sorğu O(1), amma yeniləmə O(n)) yaraşmır. Seqment ağacı və Fenvik ağacı hər iki əməliyyatı O(log n)-də edir.
![[5 2 7 1 4 3 6 8] üçün cəm ağacı: [2, 6) sorğusu iki hazır düyünü götürür, 8 və 7](img/lessons/algorithms/segment-fenwick-trees-segment.svg)
Sadə üsulların qiyməti
import math
n = 100_000 # array size
q = u = 100_000 # queries and updates
print("naive sums: ", q * n)
print("prefix sums: ", u * n)
print("segment tree: ", (q + u) * math.ceil(math.log2(n)))naive sums: 10000000000
prefix sums: 10000000000
segment tree: 3400000| Üsul | Sorğu | Yeniləmə | Tikinti |
|---|---|---|---|
| naiv cəm | O(n) | O(1) | O(1) |
| prefiks cəmləri | O(1) | O(n) | O(n) |
| seqment ağacı | O(log n) | O(log n) | O(n) |
| Fenvik ağacı | O(log n) | O(log n) | O(n log n) |
