Segment Tree Intro

Segment tree helps answer range queries fast.

Example questions: - sum from index 2 to 7? - minimum in range?

Why needed Without it: each query scans range (slow). With tree: logarithmic time.

Build simple sum tree ```python class SegTree: def __init__(self, arr): self.n = len(arr) self.t = [0] * (4*self.n) self._build(arr, 1, 0, self.n-1)

def _build(self, arr, v, l, r): if l == r: self.t[v] = arr[l] else: m = (l+r)//2 self._build(arr, v*2, l, m) self._build(arr, v*2+1, m+1, r) self.t[v] = self.t[v*2] + self.t[v*2+1] ```

Graph: segment ranges ```mermaid flowchart TD A[0..7] A --> B[0..3] A --> C[4..7] ```

Remember - segment tree = divide ranges - good for many queries + updates