Range Query

To query range $[l, r]$, traverse the tree:

• If current segment is completely inside $[l, r]$: return this node's value
• If current segment is completely outside $[l, r]$: return identity (0 for sum, $\infty$ for min)
• Otherwise: recurse on both children and combine results

def query(node, start, end, l, r):
    if r < start or end < l:
        return 0 # outside query range
    if l <= start and end <= r:
        return tree[node] # completely inside
    mid = (start + end) // 2
    leftSum = query(2*node, start, mid, l, r)
    rightSum = query(2*node+1, mid+1, end, l, r)
    return leftSum + rightSum

Time: $O(\log n)$. At each level, you visit at most 4 nodes (2 partial on left boundary, 2 on right).