#include <unordered_map>

struct Tree {
  int n;
  std::unordered_map<int, int> t; // [0..1e9]

  Tree( int n ) : n(n) {
    //t = new int[4 * n]();
  }

  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);
  }
};