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.
Where it lands in Jayverse
- Rabbit/Devnet: pick the state that gets persistent-segment-tree treatment. Make session-key/mandate balances or nonce state on the indexer persistent-segment-tree-backed, so a reorg on the Anvil devnet rolls back at O(log n) instead of a full re-index.
- Verex: use a lazy segment tree for order-book aggregates. Best bid/ask and depth-in-range are a range-sum/range-min workload; reach for a lazy segment tree instead of recomputing aggregates on every order.
- gitboard: use it as the answer to "state at block N." When gitboard needs a past state for a given service, treat the persistent segment tree as the structure to reach for, instead of snapshotting the whole database.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| push down | (보류된 연산을) 아래로 내려보내다·전파하다 · 지연 전파(lazy propagation)의 핵심 동작을 가리키는 구동사. "only pushing it down when that child" |
| composable | 조합 가능한 · 여러 연산을 순서대로 합쳐도 문제 없이 처리될 수 있어야 함을 가리킴. "pending operations must be composable" |
| collapse under | ~를 못 견디고 무너지다 · 순진한 구현이 비용을 감당 못 해 무너지는 상황. "a naive implementation collapses under O(n) cost" |
| path copying | 경로 복사(변경된 경로만 새로 만드는 기법) · 영속 자료구조가 공간을 아끼는 핵심 기법. "the previous version via path copying" |
| cross-check | 교차 검증하다 · 무작위 테스트로 결과를 다른 방식과 대조 확인할 때. "cross-check queries against arbitrary past versions" |
| roll back to | ~로 되돌리다 · 특정 시점(블록 높이)의 상태로 복귀시키는 동작. "roll back to the aggregated state" |
| point-in-time (snapshots) | 특정 시점 기준의 (스냅샷) · 과거 어느 시점 상태를 그대로 조회할 수 있음을 가리킴. "needs rollback or point-in-time snapshots" |
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/.