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 space to be safe.
For leaves, you need nodes in a perfect binary tree, but since might not be a power of 2, you allocate extra.
Some implementations use space with a different indexing scheme. Both work; the approach is simpler to reason about. Time: . Space: .