root = [1..n]

v = [l..r]
m = (l + r) / 2
v.l = [l..m]
v.r = [m+1..r]

if (l == r) // v is a leave
  v.x = a[l]

Node Change( Node v, int i, int x )
{
  // v : [l..r]
  if (l == r)
    return new Node(x) 
  m = (l + r) / 2
  if (i <= m)
    return new Node(Change(v.l, i, x), v.r);
  else
    return new Node(v.l, Change(v.r, i, x));
}