リリース・改善中
セグメント木 ガイド · 4/6
この章は現在、英語でのみ提供しています。
This chapter analyzes the time and space cost of a segment tree and compares it with other structures that solve the same problems. The goal is a clear rule of thumb for choosing between them.
| Operation | Recursive tree | Iterative tree | Note |
|---|---|---|---|
| Build | O(n) | O(n) | one combine per node |
| Point update | O(log n) | O(log n) | one leaf-to-root path |
| Range query | O(log n) | O(log n) | at most two nodes per level enter the result |
| Range update (lazy) | O(log n) | awkward | usually written recursively |
Best, average, and worst cases barely differ. A query of length 1 still walks down to a leaf and a whole-array query stops at the root, but both stay within O(log n); only the constant changes.
In the recursive query, the only nodes that partly overlap the query are those containing its left or right endpoint. Each level has at most two such nodes, so each level contributes at most four visited nodes. With about log2 n levels, the total is bounded by roughly 4 log2 n. You can check this empirically:
import math
import random
n = 1 << 16
tree = [1] * (4 * n) # values do not matter, we only count visits
visits = 0
def query(node, lo, hi, l, r):
global visits
visits += 1
if r <= lo or hi <= l:
return 0
if l <= lo and hi <= r:
return tree[node]
mid = (lo + hi) // 2
return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid, hi, l, r)
worst = 0
for _ in range(2000):
l = random.randrange(n)
r = random.randrange(l + 1, n + 1)
visits = 0
query(1, 0, n, l, r)
worst = max(worst, visits)
print(worst, 4 * math.log2(n)) # e.g. 63 64.02n - 1 nodes, but with 1-based numbering the indices can exceed 2n when n is not a power of two, so 4n slots are the usual allocation. Exactly 2 * 2^ceil(log2 n) slots are enough.2n slots.n + 1 slots.import math
def recursive_size(n):
return 2 * (1 << math.ceil(math.log2(n))) if n > 1 else 2
for n in [8, 9, 1000, 100_000]:
print(n, recursive_size(n), 4 * n, 2 * n, n + 1)
# 8 16 32 16 9
# 9 32 36 18 10
# 1000 2048 4000 2000 1001
# 100000 262144 400000 200000 100001| Structure | Build | Point update | Range query | Range update | Extra memory | Operations |
|---|---|---|---|---|---|---|
| Plain array | - | O(1) | O(n) | O(n) | none | anything |
| Prefix sums | O(n) | O(n) | O(1) | O(n) | n + 1 | invertible (sum, XOR) |
| Sparse table | O(n log n) | not supported | O(1) | not supported | n log n | idempotent (min, max, GCD) |
| Sqrt decomposition | O(n) | O(1) | O(sqrt n) | O(sqrt n) | sqrt n | most |
| Fenwick tree | O(n) | O(log n) | O(log n) | with a variant | n + 1 | invertible, like sums |
| Segment tree | O(n) | O(log n) | O(log n) | O(log n) with lazy | 2n to 4n | any associative operation |
A Fenwick tree has the same asymptotic cost as a segment tree, but its code is shorter, it uses half the memory or less, and it tends to run faster in practice. A segment tree is more flexible: it handles minimum and maximum queries and complex range updates.
In Python, with n = 200,000 and 200,000 queries, the iterative segment tree finishes within a few seconds depending on the machine. Doing the same with a plain array needs tens of thousands of additions per query on average, more than ten billion in total, which effectively never finishes. Try it yourself:
import random
import time
n, q = 200_000, 200_000
a = [random.randint(1, 100) for _ in range(n)]
tree = [0] * n + a
for i in range(n - 1, 0, -1):
tree[i] = tree[2 * i] + tree[2 * i + 1]
start = time.perf_counter()
for _ in range(q):
l = random.randrange(n)
r = random.randrange(l + 1, n + 1)
lo, hi, total = l + n, r + n, 0
while lo < hi:
if lo & 1:
total += tree[lo]; lo += 1
if hi & 1:
hi -= 1; total += tree[hi]
lo //= 2; hi //= 2
print(f"{time.perf_counter() - start:.2f}s")A segment tree builds in O(n), answers point updates and range queries in O(log n), and uses 2n to 4n memory. The usual rule: static data calls for prefix sums or a sparse table, sums with point updates call for a Fenwick tree, and minimums, maximums, or range updates call for a segment tree.
コメント 0件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。