Дан массив: нужно отвечать на суммы на отрезке a[l:r] и менять отдельные элементы a[i] = v. Когда и того и другого сотни тысяч, не годятся ни наивный цикл (O(n) на запрос), ни префиксные суммы (запрос O(1), но обновление O(n)). Дерево отрезков и дерево Фенвика делают обе операции за O(log n).
![Дерево сумм для [5 2 7 1 4 3 6 8]: запрос [2, 6) берёт два готовых узла, 8 и 7](img/lessons/algorithms/segment-fenwick-trees-segment.svg)
Цена простых методов
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| Подход | Запрос | Обновление | Построение |
|---|---|---|---|
| наивная сумма | O(n) | O(1) | O(1) |
| префиксные суммы | O(1) | O(n) | O(n) |
| дерево отрезков | O(log n) | O(log n) | O(n) |
| дерево Фенвика | O(log n) | O(log n) | O(n log n) |
