Problem - Version Queries

Given a sequence of operations:

• update i x: Set $A[i] = x$
• query v l r: Sum of $A[l..r]$ after version $v$ (0-indexed, version 0 is initial)

Example:

Initial: $A = [1, 2, 3]$

update 1 5 (version 1): $A = [1, 5, 3]$

update 2 7 (version 2): $A = [1, 5, 7]$

query 0 0 2 returns $6$ (version 0: $[1, 2, 3]$)

query 1 0 2 returns $9$ (version 1: $[1, 5, 3]$)

Use persistent segment tree. Each update creates a new version.