【模板】树状树组

 

template<typename T> struct BIT {
	T *s; int lim;
	void init(int x) { lim = x, s = new T[x + 1], memset(s, 0, (lim + 1) * sizeof(int)); }
	void update(int x, T c) { for(;x <= lim; x += x & -x)s[x] += c; }
	T query(int x) { T ans = 0; for(; x; x -= x & -x)ans += s[x]; return ans; }
};