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

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

flowchart TD
  A[0..7]
  A --> B[0..3]
  A --> C[4..7]

Remember

• segment tree = divide ranges
• good for many queries + updates