Lançado · em melhoria
Guia de Árvores de segmentos · 1/6
Por enquanto, este capítulo está disponível apenas em inglês.
A segment tree is a data structure that answers questions about contiguous ranges of an array, such as "what is the sum of elements 3 through 7?" or "what is the minimum in this range?", and keeps those answers fast even while the array keeps changing. This chapter explains why you need one, what it looks like, and the vocabulary used in the rest of the guide.
Suppose an array of length n receives a long stream of two kinds of requests:
a[i].a[l] through a[r-1].The simplest approach keeps the plain array and loops over the range for every query. Updates cost O(1), but each query costs O(n).
a = [5, 3, 7, 9, 6, 4, 1, 2]
def update(i, value):
a[i] = value # O(1)
def query(l, r):
return sum(a[l:r]) # O(n): adds every element in the rangeIf the values never change, prefix sums are hard to beat. Store in prefix[i] the sum of the first i elements, and any range sum becomes a single subtraction. The catch is that changing one element invalidates every prefix sum after it, so an update costs O(n).
from itertools import accumulate
a = [5, 3, 7, 9, 6, 4, 1, 2]
prefix = [0, *accumulate(a)] # [0, 5, 8, 15, 24, 30, 34, 35, 37]
def query(l, r):
return prefix[r] - prefix[l] # O(1)
def update(i, value):
diff = value - a[i]
a[i] = value
for k in range(i + 1, len(prefix)): # O(n): fix every later prefix
prefix[k] += diff
print(query(2, 6)) # 26| Approach | Point update | Range query | Good fit |
|---|---|---|---|
| Plain array | O(1) | O(n) | Queries are rare |
| Prefix sums | O(n) | O(1) | Values never change |
| Segment tree | O(log n) | O(log n) | Updates and queries interleave |
Instead of making one operation extremely fast and the other slow, a segment tree makes both operations `O(log n)`. With hundreds of thousands of requests, that is the difference between seconds and hours.
A segment tree is a binary tree in which every node is responsible for one range of the array and stores a of that range (its sum, minimum, and so on).
[0, n).[lo, hi) splits at the midpoint mid: the left child covers [lo, mid) and the right child covers [mid, hi).Because each split halves the range, the tree has height about log2 n. Any query range can be covered by a handful of disjoint nodes (at most two per level), and changing one element only requires recomputing the single path from that leaf to the root. That is why both operations run in O(log n).
The operation stored in the tree must be associative, and the implementation is cleanest when it also has an identity element. In algebra this structure is called a monoid.
import math
# (combine function, identity)
SUM = (lambda x, y: x + y, 0)
MIN = (min, math.inf)
MAX = (max, -math.inf)
GCD = (math.gcd, 0)
XOR = (lambda x, y: x ^ y, 0)
op, identity = MIN
print(op(op(4, 9), 2) == op(4, op(9, 2))) # True: associativity
print(op(identity, 7)) # 7: the identity changes nothingA question like "what is the median of this range?" does not fit: the parent's answer cannot be computed from the two children's summaries alone, so a basic segment tree cannot answer it.
If the values never change, prefix sums or a sparse table are simpler and faster.
A segment tree stores a summary for every range obtained by repeatedly halving the array, which makes both point updates and range queries O(log n). As long as the combine operation is associative and has an identity, the same structure answers sums, minimums, maximums, GCDs, and more. The next chapter builds a tree by hand and traces queries and updates through it.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.