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