树状数组是一个擅长单改区查的数据结构。

树状数组只能存满足可差分性的数据（如前缀和）。树状数组其实就是前缀和升级版，它相比于前缀和可以存动态数据（修改快）。

树状数组基本形态：

类模板

如果报错，请删除第 3 行。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long size_t;
template<typename tp>
class BIT{
	private:
		size_t n;
		vector<tp> c;
		size_t lowbit(size_t x){
			return x & -x;
		}
	public:
		BIT(size_t n){
			this->n = n;
			c = vector<tp>(n);
		}
		BIT(vector<tp> a){
			n = a.size();
			for (size_t i = 1;i <= n;i++){
				add(i,a[i]);
			}
		}
		BIT(tp *a,size_t n){
			this->n = n; 
			for (size_t i = 1;i <= n;i++){
				add(i,a[i]);
			}
		}
		BIT(BIT<tp> &a){
			n = a.size();
			c = a;
		}
		size_t size(){
			return n;
		}
		void add(size_t i,tp val){
			for (;i <= n;i += lowbit(i))
				c[i] += val;
		}
		tp query(size_t r){
			tp res = 0;
			for (;r;r -= lowbit(r))
				res += c[r];
			return res;
		}
		tp query(size_t l,size_t r){
			return query(r) - query(l - 1);
		}
};