When array values are huge (e.g., to ) but sparse, pre-allocating nodes wastes memory.
Dynamic segment trees create nodes only when needed:
class Node:
def __init__(self):
self.val = 0
self.left = None # lazy: create on demand
self.right = None
def update(node, start, end, idx, val):
if start == end:
node.val = val
return
mid = (start + end) // 2
if idx <= mid:
if not node.left:
node.left = Node()
update(node.left, start, mid, idx, val)
else:
if not node.right:
node.right = Node()
update(node.right, mid+1, end, idx, val)
left_val = node.left.val if node.left else 0
right_val = node.right.val if node.right else 0
node.val = left_val + right_val
Space: for updates on range .