Query with Lazy

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 $O(\log n)$ per query and per range update.