Like heaps, segment trees use array indexing:
- Root is at index 1 (or 0, depending on convention)
- Left child of node :
- Right child of node :
- Parent of node :
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)$.