To query range , traverse the tree:
- If current segment is completely inside : return this node's value
- If current segment is completely outside : return identity (0 for sum, 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: . At each level, you visit at most 4 nodes (2 partial on left boundary, 2 on right).