1 Build + Point Update + Range Sum

build(node, lo, hi):
    if lo == hi:  tree[node] = arr[lo]; return
    mid = (lo + hi) / 2
    build(left);  build(right)
    tree[node] = left.sum + right.sum

update(i, val):   walk down to leaf i, fix sums on the way back up

query(l, r):
    disjoint      → identity (0 for sum)
    fully inside  → tree[node]
    else          → combine children answers

Time: build O(n), update O(log n), query O(log n)

public int query(int node, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return 0;
    if (l <= lo && hi <= r) return tree[node];

    int mid = (lo + hi) / 2;
    return query(node*2, lo, mid, l, r) +
           query(node*2+1, mid+1, hi, l, r);
}

def query(self, node, lo, hi, l, r):
    if r < lo or hi < l:
        return 0
    if l <= lo and hi <= r:
        return self.tree[node]

    mid = (lo + hi) // 2
    return (self.query(node * 2, lo, mid, l, r) +
            self.query(node * 2 + 1, mid + 1, hi, l, r))

int query(int node, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return 0;
    if (l <= lo && hi <= r) return tree[node];

    int mid = (lo + hi) / 2;
    return query(node*2, lo, mid, l, r) +
           query(node*2+1, mid+1, hi, l, r);
}

query(node, lo, hi, l, r) {
  if (r < lo || hi < l) return 0;
  if (l <= lo && hi <= r) return this.tree[node];

  const mid = (lo + hi) >> 1;
  return (
    this.query(node * 2, lo, mid, l, r) +
    this.query(node * 2 + 1, mid + 1, hi, l, r)
  );
}

2 Lazy Propagation (Range Add + Range Sum)

apply(node, delta):  tree[node] += delta * segLen;  lazy[node] += delta

push(node):          move pending lazy tag to both children, clear it

update(l, r, d):
    stop at fully covered node → apply(d)
    else push(), recurse both sides, recombine

query(l, r):
    push() before reading below a node, then combine

Key idea: a node with a pending tag “looks correct” from outside — children are only fixed when someone descends.

3 Swap-the-Combiner Checklist

Everything else in the template stays identical.

4 Sizing & Indexing Rules

• Allocate 4 * n for recursive trees — always safe.
• Node 1 = root; children of node are node*2, node*2 + 1.
• Leaves live at different depths — never assume row order.