Dynamic Segment Trees

When array values are huge (e.g., $0$ to $10^9$) but sparse, pre-allocating $4n$ nodes wastes memory.

Dynamic segment trees create nodes only when needed:

class Node:
    function init():
        this.val = 0
        this.left = null // lazy: create on demand
        this.right = null

function update(node, start, end, idx, val):
    if start == end:
        node.val = val
        return
    mid = floor((start + end) / 2)
    if idx <= mid:
        if node.left == null:
            node.left = new Node()
        update(node.left, start, mid, idx, val)
    else:
        if node.right == null:
            node.right = new Node()
        update(node.right, mid+1, end, idx, val)
    leftVal = (node.left != null) ? node.left.val : 0
    rightVal = (node.right != null) ? node.right.val : 0
    node.val = leftVal + rightVal

Space: $O(Q \log N)$ for $Q$ updates on range $[0, N)$.