Nested summaries of a shelf
Segment Trees
The analogy
A long shelf of numbers. Someone keeps asking "what is the total between slot 3 and slot 9?" and also keeps changing individual slots. Instead of re-adding every time, you keep a pyramid of pre-computed totals: totals for pairs, then for quarters, then the whole shelf. Any range is a handful of those pre-computed blocks, and changing one slot only invalidates the blocks above it.
Visualizer
The pyramid of sums
step 1 / 8The array [3, 1, 4, 1, 5, 9] with a pyramid of sums above it. Each node stores the total of the range it covers.leaves = the array, root = total 26
class SegTree:
def __init__(self, a):
self.n = len(a)
self.t = [0] * (4 * self.n)
self._build(a, 1, 0, self.n - 1)
def _build(self, a, node, lo, hi):
if lo == hi:
self.t[node] = a[lo]; return
mid = (lo + hi) // 2
self._build(a, 2*node, lo, mid)
self._build(a, 2*node+1, mid + 1, hi)
self.t[node] = self.t[2*node] + self.t[2*node+1]
def query(self, node, lo, hi, l, r):
if r < lo or hi < l: return 0 # disjoint
if l <= lo and hi <= r: return self.t[node] # fully inside
mid = (lo + hi) // 2
return (self.query(2*node, lo, mid, l, r) +
self.query(2*node+1, mid + 1, hi, l, r))Check yourself
The array never changes, but you get millions of range-sum queries. Best tool?