struct Tree {
  int n, *t;

  Tree( int n, int *a ) : n(n) {
    t = new int[4 * n]();
    build(1, n, a);
  }

  int build( int v, int n, int *a ) {
    if (n == 1)
      t[v] = a[0];
    else {
      int m = n / 2;
      t[v] = build(2 * v, m, a) + build(2 * v + 1, n - m, a + m);
    }
  }

  int change( int v, int vl, int vr, int i, int x ) { // [vl, vr)
    if (i < vl || vr <= i)
      return t[v];
    if (vr - vl == 1)
      return t[v] = x;
    int vm = (vl + vr) / 2;
    return t[v] = change(2 * v + 0, vl, vm, i, x) + change(2 * v + 1, vm, vr, i, x);
  }

  void change( int i, int x ) {
    change(1, 0, n, i, x);
  }

  int get( int v, int vl, int vr, int l, int r ) { // [vl, vr) [l, r)
    if (r <= vl || vr <= l)
      return 0;
    if (l <= vl && vr <= r)
      return t[v];
    int vm = (vl + vr) / 2;
    return get(2 * v + 0, vl, vm, l, r) + get(2 * v + 1, vm, vr, l, r);
  }

  int get( int l, int r ) { // [l, r)
    return get(1, 0, n, l, r);
  }
};