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:
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: for updates on range .