Given an array, we must answer sums on a range a[l:r] and change single elements a[i] = v. If there are hundreds of thousands of both, neither the naive loop (O(n) per query) nor prefix sums (O(1) per query but O(n) per update) is good enough. A segment tree and a Fenwick tree make both operations O(log n).
![A sum tree for [5 2 7 1 4 3 6 8]: the query [2, 6) takes two ready nodes, 8 and 7](img/lessons/algorithms/segment-fenwick-trees-segment.svg)
The price of the simple methods
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| Approach | Query | Update | Build |
|---|---|---|---|
| naive sum | O(n) | O(1) | O(1) |
| prefix sums | O(1) | O(n) | O(n) |
| segment tree | O(log n) | O(log n) | O(n) |
| Fenwick tree | O(log n) | O(log n) | O(n log n) |
