Advanced Segment Trees TODO
Concept
A segment tree is a binary-tree structure that answers queries and updates over an associative operation on array ranges (sum, min, gcd, and so on) in O(log n). Lazy propagation handles whole-range updates by storing, at each node, a pending operation that hasn't yet been pushed down to its children, and only pushing it down when that child is actually visited — which keeps range updates at O(log n) too. For this to work, pending operations must be composable, and it must be defined how they affect a node's stored value depending on the range size (for a range-add, for instance, you add delta times the range length to the sum). A persistent segment tree creates only the O(log n) nodes along the root-to-leaf path on each update and shares the rest of the subtrees with the previous version via path copying, preserving every past version at only O(log n) extra space per update. That makes it possible to query any past version, which is widely used for finding the k-th element or computing a rank within a range.
For state aggregation that needs rollback or point-in-time snapshots, and for workloads with heavy range updates, a naive implementation collapses under O(n) cost per update.
Code & Formula
# Day 10: 세그먼트 트리 심화 — Lazy Propagation으로 구간 갱신·구간 합을 O(log n)에 처리
# 보류값(lazy)을 노드에 쌓아두고 실제 방문 시점에만 자식으로 밀어내려 구간 갱신 비용을 낮춘다.
class LazySegTree:
def __init__(self, n):
self.sum = [0] * (4 * n)
self.lazy = [0] * (4 * n)
def _push_down(self, node, lo, hi):
if self.lazy[node] == 0:
return
mid = (lo + hi) // 2
for child, clo, chi in ((node * 2, lo, mid), (node * 2 + 1, mid + 1, hi)):
self.lazy[child] += self.lazy[node]
self.sum[child] += self.lazy[node] * (chi - clo + 1)
self.lazy[node] = 0
def range_add(self, node, lo, hi, l, r, delta):
if r < lo or hi < l:
return
if l <= lo and hi <= r:
self.sum[node] += delta * (hi - lo + 1)
self.lazy[node] += delta
return
self._push_down(node, lo, hi)
mid = (lo + hi) // 2
self.range_add(node * 2, lo, mid, l, r, delta)
self.range_add(node * 2 + 1, mid + 1, hi, l, r, delta)
self.sum[node] = self.sum[node * 2] + self.sum[node * 2 + 1]
def range_sum(self, node, lo, hi, l, r):
if r < lo or hi < l:
return 0
if l <= lo and hi <= r:
return self.sum[node]
self._push_down(node, lo, hi)
mid = (lo + hi) // 2
return (self.range_sum(node * 2, lo, mid, l, r) +
self.range_sum(node * 2 + 1, mid + 1, hi, l, r))
n = 10
tree = LazySegTree(n)
tree.range_add(1, 0, n - 1, 2, 5, 3) # 인덱스 2~5에 +3
tree.range_add(1, 0, n - 1, 0, 9, 1) # 전체 구간에 +1
print("구간 합 [0,9] =", tree.range_sum(1, 0, n - 1, 0, 9), "(기대값: 3*4 + 1*10 = 22)")
print("구간 합 [2,5] =", tree.range_sum(1, 0, n - 1, 2, 5), "(기대값: (3+1)*4 = 16)")
print("구간 합 [6,9] =", tree.range_sum(1, 0, n - 1, 6, 9), "(기대값: 1*4 = 4)")
docs/code/algorithms/algorithms-10.py
Exercise
Implement a lazy segment tree that supports range-add and range-sum, then build a persistent version of the same operations, and cross-check queries against arbitrary past versions with randomized tests against a brute-force reference.
Practical Connection
When an indexer has to roll back to the aggregated state at a specific block height due to a chain reorg, a version-sharing structure lets it maintain snapshots at O(log n) cost instead of copying everything.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.