数据结构——树状数组

前言：

树状数组，利用二进制乱七八糟的东西的数据结构。

trick：

修改，查询：

​ 区间修改和单点修改分开来说，区间修改相当于树状数组维护的是一个差分数组，区间修改对应的单点查询，单点修改对应的区间查询，前者是维护差分数组，后者维护的是原本的数组，这次不过多赘述，因为如果树状数组是以下标进行维护的话，那本人更习惯使用线段树。大多数还是权值树状数组用的更多一些。

查询第k大（小）值：

​ （来自https://www.cnblogs.com/LiuRunky/p/BIT_Find_kth.html）

如图所示，由于树状数组的特性，最高位的1所在的位置会存储到所有数字的个数。所以我们可以像倍增那样，i从大往小，设当前位置是x，则如果F[x+i]<k，那么就进行下去。进行下去的话，x+=i。接着继续。

int find(int k){int x=0,sum=0;if(qry(0,n)<k || k<=0) return -114514;for(int i=1<<std::__lg(n);i;i/=2){//这里是小于而没有等于号是因为我们要找到最右边小于k的数然后再+1才是我们要的答案，但是又因为这里树状数组整体下标+1了已经（因为这样可以解决下标0）所以直接return x。if(x+i<=n and sum+F[x+i]<k){sum+=F[x+i];x+=i;}}return x;}

二维查询k大：

倘若我们有一个矩阵，要查询这个矩阵横坐标在l，r之间的k大数该怎么办呢？我们可以用到二维树状数组。

直接贴代码先：

int suan(int x,int i){int sum=0;for(int q=x;q>=1;q-=fan(q)) sum+=F[q][i];return sum;
}
int find(int l,int r,int k){l+=1,r+=1;int y=0,sum=0;for(int i=1<<std::__lg(m);i;i/=2){int tem=suan(r,y+i)-suan(l-1,y+i);if(y+i<=m and sum + tem < k){sum+=tem;y+=i;}}return y;
}

用举例去说明，我们知道最高位的1所在的位置会存储到所有数字的个数。但是二维的怎么做呢？我们总不能直接用\(F[r][i]-F[l-1][i]\)，因为我们需要表示前r行里前i个的数，第二维是能够直接代表第r行的所有数字，但是第一维的r因为lowbit不是0，所以我们不能直接使用，需要qry，所以我们要用suan（）函数处理出来，对r进行qry，l也是同理。

模板：

一维树状数组：

class tree {vector<int> F;int n;int fan(int x) { return x & -x; }int get(int x) {x += 1; int tem = 0; for (int i = x; i >= 1; i -= fan(i)) tem += F[i];return tem;}
public:void init(int n_) {vector<int>().swap(F);n=n_+1;F.resize(n + 5);}void add(int x, int val) {x += 1; for (int i = x; i <=n; i += fan(i)) F[i] += val;}int qry(int l, int r) {if (l > r) return 0; if (l - 1 < 0) return get(r);return get(r) - get(l - 1);}int find(int k){int x=0,sum=0;if(qry(0,n)<k || k<=0) return -114514;for(int i=1<<std::__lg(n);i;i/=2){if(x+i<=n and sum+F[x+i]<k){sum+=F[x+i];x+=i;}}return x;}
}shu;

二维树状数组：

class tree {vector<vector<int> > F;int n,m;int fan(int x) { return x & -x; }int get(int x,int y){x+=1,y+=1;int tem=0;for(int i=x;i>=1;i-=fan(i))for(int j=y;j>=1;j-=fan(j)){tem+=F[i][j];}return tem;}
public:void init(int n_,int m_) {n=n_+1,m=m_+1;F.reserve(n+10);rep(i,1,n) F[i].assign(m+10,0);}void add(int x,int y, int val) {x+=1,y+=1;for(int i=x;i<=n;i+=fan(i)){for(int j=y;j<=m;j+=fan(j)){F[i][j]+=val;}}}int qry(int x1, int y1,int x2,int y2) {return get(x2,y2)-get(x1-1,y2)-get(x2,y1-1)+get(x1-1,y1-1);}
}shu;