Query must push down before recursing:
def query(node, start, end, l, r):
if r < start or end < l:
return 0
if l <= start and end <= r:
return tree[node]
pushDown(node, start, end)
mid = (start + end) // 2
return (query(2*node, start, mid, l, r) +
query(2*node+1, mid+1, end, l, r))
The only change from non-lazy query: call pushDown before accessing children.
This guarantees any pending updates are applied before we compute the answer.
Time: still per query and per range update.