TreesTrees

Segment Tree (range sum)

A binary tree over array intervals that answers range queries (sum, min, max, gcd) and point or range updates in O(log n).

Learn Segment Tree →

Array | commands — "numbers | query l r, update i v" — 0-based indices, inclusive ranges

Empty tree

Array a

531014628

1/65Build a sum segment tree over 8 elements. Each node stores the sum of a range; a leaf covers one index and the root covers [0,7].

Visiting (partial overlap / recursing)Fully covered — take its sumNo overlap — prunedRecomputed after update

PseudocodeLearn Segment Tree →

1build(node, l, r): if l == r: tree[node] = a[l]
2  else: build children over [l,mid], [mid+1,r]; tree[node] = left + right
3query(node, l, r, ql, qr):
4  if qr < l or r < ql: return 0            # no overlap
5  if ql <= l and r <= qr: return tree[node] # total overlap
6  return query(left) + query(right)         # partial overlap: split
7update(node, l, r, i, v): descend to leaf i, set it, recompute sums on the way up

Variables

Complexity

access O(log n)

search O(n)

insert —

delete —

Speed