树状数组

const ll N = 1333;
int n;
struct BIT {
	int tag[MAXN], t[MAXN], Tag;
	void reset() { ++Tag; }
	void add(int k, int v) {
	  while (k <= n) {
		if (tag[k] != Tag) t[k] = 0;
		t[k] += v, tag[k] = Tag;
		k += lowbit(k);
	  }
	}
	int getsum(int k) {
	  int ret = 0;
	  while (k) {
		if (tag[k] == Tag) ret += t[k];
		k -= lowbit(k);
	  }
	  return ret;
	}

}T;