Array Representation

Like heaps, segment trees use array indexing:

• Root is at index 1 (or 0, depending on convention)
• Left child of node $i$: $2i$
• Right child of node $i$: $2i + 1$
• Parent of node $i$: $\lfloor i/2 \rfloor$

class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (4 * n)
``` We allocate $4n$ space to be safe. 

For $n$ leaves, you need $2n - 1$ nodes in a perfect binary tree, but since $n$ might not be a power of 2, you allocate extra. 

Some implementations use $2n$ space with a different indexing scheme. Both work; the $4n$ approach is simpler to reason about. Time: $O(\log n)$. Space: $O(n)$.