介绍
树状数组的推导
两个基础操作
模板-acwing795. 前缀和
#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
int c[N]; int lowbit(int x){return x & -x;
}int query(int x){int ans = 0;for(; x; x -= lowbit(x)) ans += c[x];return ans;
}void add(int x,int y){for(; x <= N; x += lowbit(x)) c[x] += y;
}int main(){int n,m; scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++){int num; scanf("%d",&num);add(i,num);}while(m--){int l,r; scanf("%d%d",&l,&r);printf("%d\n",query(r)-query(l-1));}return 0;
} 模板-acwing5910. 求逆序对
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N = 1e6+10;
LL c[N],a[N];int lowbit(int x) // 返回末尾的1
{return x & -x;
}LL query(int x){LL ans = 0;for(; x; x -= lowbit(x)) ans += c[x];return ans;
}void add(int x,int y){for(; x <= N; x += lowbit(x)) c[x] += y;
}int main()
{LL ans = 0;int n; scanf("%d",&n);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);}//倒序扫描，找值比当前这个数小但是先进入树状数组的数，即1-（a[i]-1）的和，加入ans（根据逆序对的定义构造的）for(int i = n; i >= 1; i--){ans += query(a[i]-1)-query(0);add(a[i],1);}printf("%lld\n",ans);return 0;
}例题
A. 数列操作
思路
模板题，套树桩数组的模板即可。注意开long long
代码
#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
long long c[N]; int lowbit(int x){return x & -x;
}long long query(int x){long long ans = 0;for(; x; x -= lowbit(x)) ans += c[x];return ans;
}void add(int x,int y){for(; x <= N; x += lowbit(x)) c[x] += y;
}int main(){long long n,m; scanf("%lld%lld",&n,&m);for(int i = 1; i <= n; i++){long long x; scanf("%lld",&x);add(i,x);}while(m--){long long t,idx,x,l,r; scanf("%lld",&t);if(t == 1){scanf("%lld%lld",&idx,&x);add(idx,x);}else{scanf("%lld%lld",&l,&r);printf("%lld\n",query(r)-query(l-1));}}return 0;
} B. 数星星 Stars
思路
这道题的求解思路跟逆序对那道题差不多，都是利用树状数组去查1-x的和，但是这道题要考虑好一种类似谈心的思路，就是他要找左下角的星星个数，他输入时是按照y增序，y相同时按照x增序给出，那么某个星星的等级就是x坐标1-x的星星个数，但是要注意的是这道题有可能会坐标会为0那么就会出现越界问题，所以每次要给x坐标+1，但是整体每个数的大小关系并不会改变。
代码
#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
long long c[N],lv[N]; int lowbit(int x){return x & -x;
}long long query(int x){long long ans = 0;for(; x; x -= lowbit(x)) ans += c[x];return ans;
}void add(int x,int y){for(; x <= N; x += lowbit(x)) c[x] += y;
}int main(){int n; cin >> n;for(int i = 1; i <= n; i++){int x,y; cin >> x >> y;x++;int t = query(x);lv[t]++;add(x,1);}for(int i = 0; i < n; i++) cout << lv[i] << endl;return 0;
} C. 校门外的树
思路
这道题因为是求某个区间内树的数量，树在区间内的具体位置是不知道的，所以用两个数组分别表示该点左侧树的数量和该点右侧树的数量，区间[a,b]内树的数量=b点左侧树的数量 – (a-1)点右侧树的数量。之所以是a-1点不是a点是因为要算上a点上的树。
代码
#include <bits/stdc++.h>
using namespace std;
int const N = 50010;
int n, m;
// 树状数组模板
int c1[N], c2[N];#define lowbit(x) (x & -x)
typedef long long LL;void add(int c[], int x, int v) {while (x < N) c[x] += v, x += lowbit(x);
}LL sum(int c[], int x) {LL res = 0;while (x) res += c[x], x -= lowbit(x);return res;
}//这道题因为是求某个区间内树的数量，树在区间内的具体位置是不知道的
//所以用两个数组分别表示该点左侧树的数量和该点右侧树的数量
//区间[a,b]内树的数量=b点左侧树的数量 – (a-1)点右侧树的数量。之所以是a-1点不是a点是因为要算上a点上的树。int main() {int k, l, r;scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) {scanf("%d%d%d", &k, &l, &r);if (k == 1)add(c1, l, 1), add(c2, r, 1); // c1记录左括号的个数，c2记录右括号的个数elseprintf("%d\n", sum(c1, r) - sum(c2, l - 1));}return 0;
}D. 清点人数
思路
模板题，直接套模板。开long long
代码
#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
long long c[N],lv[N]; int lowbit(int x){return x & -x;
}long long query(int x){long long ans = 0;for(; x; x -= lowbit(x)) ans += c[x];return ans;
}void add(int x,int y){for(; x <= N; x += lowbit(x)) c[x] += y;
}int main(){int n,k; cin >> n >> k;for(int i = 1; i <= k; i++){char t;int m,p;cin >> t;if(t == 'A'){scanf("%d",&m);printf("%d\n",query(m));}else if(t == 'B'){scanf("%d%d",&m,&p);add(m,p);}else {scanf("%d%d",&m,&p);add(m,-p);}}return 0;
} E. 简单题
思路
这道题可能是这几道题中较难的一道，这道题如果不是取反操作的话，就是一道树状数组区间修改区间查询的题了，但是他是取反操作，我们就可以简化一下，不用像区间修改一样另开一个前缀和数组，接下来讲解本体思路：
根据差分思想，可以在从1~l先取反一次，再在1~r+1取反一次就可以得到l-r取反了，取反操作就异或上1即可（^1），求某一位的值即从1~x的异或值就第x位的值。
#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
bool c[N];
int n,m; int lowbit(int x){return x & -x;
}bool query(int x){bool ans = 0;for(; x; x -= lowbit(x)) ans ^= c[x];return ans;
}void add(int x){for(; x <= N; x += lowbit(x)) c[x] ^= 1;
}void modify(int l, int r) // 原数组的区间修改 <- 差分数组的单点修改
{add(l);if (r != n)add(r+1);
}int main(){cin >> n >> m;for(int i = 1; i <= m; i++){char t;int x,l,r;cin >> t;if(t == '2'){scanf("%d",&x);printf("%d\n",query(x));}else{scanf("%d%d",&l,&r);modify(l,r);}}return 0;
} 
