今天我们来学树状数组。
众所周知，树状数组是一个模板性很强的东西。
我们先用一道题目引入。
单点修改，区间查询
模板题
【题意】
给出n个数,并且初始化所有数字都为0。接下来m次操作。
操作有以下两种：
1：C x k 把第x个数的值增加k（k可正可负）；
2：P x y 就是询问 第x个数 至 第y个数 的所有数的和。
【输入格式】
第一行两个整数n、m(1≤n≤100000，1 ≤m≤100000)。下来m行，每行描述一次操作。
【输出格式】
当2操作时输出相应的答案。
第一种方法——暴力
很显然，暴力就可以了。主要是此题数据太水
时间复杂度：O（nm）
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005];
int main()
{
scanf("%d%d",&n,&m);
while(m--)
{
char ch[2];
int x,y;
scanf("%s%d%d",ch,&x,&y);
if(ch[0]=='C')
{
a[x]+=y;
}
else
{
int s=0;
for(int i=x;i<=y;i++)
{
s+=a[i];
}
printf("%d\n",s);
}
}
}
暴力都不会写就Go Die 吧！
优化
很显然，必须优化。可以看见，题目上写了几个字：树状数组。
那么，
树状数组是什么？
树状数组是一种用来维护区间操作的数据结构
找规律
如图，这是 一个维护和的树状数组。
从图中，可以发现很多性质，下面我来捋一捋： 
（此图来自suuon）（我不像某人那样厚颜无耻……）
- 设树状数组为c，正常数组为a。
首先我们定义一个函数 lowbit表示二进制中最右边“1”的位置
int lowbit(long long x) { return x&(-x); }- 单点修改（C操作）：
很容易看出规律：
每个增加的下标都是原有的下标 i 加上 lowbit(i) 区间查询(P操作) ：
树状数组来求 1 到 N 的区间和比较方便，但我们如何求 K 到 N 的区间和呢？ 只需要让 1 到 N 的和 减去 1到 K-1 的和。（很容易想明白，这就是前缀和思想！！！）那么，代码就可以写出来了……
代码
写了注释。
#include<bits/stdc++.h>
using namespace std;
int a[100010],c[100010];
int n,m;
int lowbit(int x)//求二进制中最右边“1”的位置
{
return x&-x;//详细原理自己查
}
void add(int x,int k)//C操作
{
a[x]+=k;//确实没必要
while(x<=n)
{
c[x]+=k;//修改每个树节点
x+=lowbit(x);//寻找自己的父节点
}
}
int summ(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x];
x-=lowbit(x);//找下级子节点
}
return ans;//返回前缀和
}
int main()
{
scanf("%d%d",&n,&m);
while(m--)
{
int x,y;
char oider[3];
//字符数组的出现有原因，自己想！
scanf("%s%d%d",oider,&x,&y);
if(oider[0]=='C') add(x,y);
else printf("%d\n",summ(y)-summ(x-1));
//summ(y)-summ(x-1)运用的是前缀和思想
}
}
有点难度，但上面是模板。背下来，多打几遍，就能理解！
接着，让我们做一道题目巩固一下。
破坏环形公路
说明
【题意】
在太平洋中心有一个圆形小岛，沿着小岛的海岸线分布着n个小镇，编号分别为1,2,3~~n；小镇i-1、小镇i、小镇i+1是相邻的（当然小镇n与小镇1相邻）。相邻小镇之间存在一条公路，公路也有编号，公路i连接小镇i和小镇i+1，公路n连接小镇n和小镇1.现在对小岛有m个操作，操作有两种：
询问操作：1 x y 代表小镇x到小镇y是否联通，联通输出1，否则输出0；
修改操作：0 x 代表修改公路x，如果公路原来是完好的，则断开，否则修好公路x。
【输入格式】
输入第一行为一个整数t，代表下来有t组数据。
每组数据第一行两个整数n，m（1≤n,m≤500000），分别表示小镇个数和操作命令数目。
输入接下来的m行，每一行代表一条操作指令。
【输出格式】
对于相邻两组数据之间要留一空行。
样例
输入数据 1
1
5 10
1 2 5
0 4
1 4 5
0 2
1 3 4
1 1 3
0 1
0 2
1 2 4
1 2 5
输出数据 1
1
1
1
0
1
0
讲两种思路
一种是理解为环形的：
不同点1数组要*2，在初始建边时，思路1需要建2n条边
不同点2 如：一个钟，算1点到3点距离，这种方法是先算整钟的距离，再减去1点到3点的距离。jc发了代码我就不发了。在代码中具体的不同在于这里的s2是x+n-y，而另外一种思路是n-y+x
二就是如下的（就是不*2，理解成是一列数）
思路二
前面三函数的就不讲了。
注意：此不同于spfa的建边，spfa是用结构体分别记录点序号和边序号，这道题是直接用点序号+1做为边，建边时没有记录点序号，由于a数组的权重都一样所以也没记录，。
so： a数组的意义自然而然就成了： //a[i]的值只有0或1，表示第i号公路（点i-1与点i之间的公路）是否存在 //注：代码中对第i号公路的定义与题意不同 //只有这句是小白菜的
#include<cstdio>
#include<cstring>
using namespace std;
int n,c[510000];
bool a[510000];
int lowbit(int x ){
return x&-x;
}
void add(int x,int k) {
while(x<=n)c[x]+=k,x+=lowbit(x);
}
int getsum(int x) {
int s=0;
while(x>=1)s+=c[x],x-=lowbit(x);
return s;
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
int m;
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
add(i,1);
a[i]=1;
}
for(int i=1;i<=m;i++) {
int k,x,y;
scanf("%d",&k);
if(k==1) {
scanf("%d%d",&x,&y);
if(x>y) swap(x,y);
int s1=getsum(y)-getsum(x);//大的前缀和 减 小的前缀和， 算出区间总和
int s2=getsum(n)-getsum(y) + getsum(x);//所以先算y到n的和 再加1到x的和
if( (s1==y-x) || (s2== (n-y) + x) ) //只要有一条通过就可以了
printf("1\n");
else printf("0\n");
}
// 例如 x=2， y=4 ，有六个点名为123456，s1是走234这条路， s2是走45612这条路 （环形） 不同在于先算y到n的和 再加1到x的和的
//由于这里的a数组只用0,1表示， 所以如果连通的话，两者和一样
// 如x=2, y=4, 在未修改路时，a数组为{1，1，1，1，1，1} 所以a[y]的前缀和-a[x]的前缀和=2 而4 - 2 也= 2。所以如果相等就连通 // 但如果不连通过就不等了
else {
int x;scanf("%d",&x);
x=x%n+1;//代入样例试试就知道了 （5%5=0）
if(a[x]==1)a[x]=0,add(x,-1);//建路
else a[x]=1,add(x,1);//破坏
}
}
printf("\n");
}
return 0;
}
补一下思路一的代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int c[1000010], n;
bool a[1000010];
int lowbit(int x) {
return x&-x;
}
void change(int x, int k) {
while(x <= (n<<1)) {
c[x] += k;
x += lowbit(x);
}
}
int sum(int x) {
int ans = 0;
while(x > 0) {
ans += c[x];
x -= lowbit(x);
}
return ans;
}
int main() {
int t, x, y, order;
scanf("%d", &t);
while(t--) {
memset(a, false, sizeof(a));
memset(c, 0, sizeof(c));
int m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n+n+1; i++) {
change(i, 1);
a[i] = true;
}
while(m--) {
scanf("%d%d", &order, &x);
if(order == 1) {
scanf("%d", &y);
if(x > y) swap(x, y);
int s1 = sum(y-1) - sum(x-1);
int s2 = sum(x+n-1) - sum(y-1);
if(s1==y-x || s2==x+n-y) printf("1\n");
else printf("0\n");
} else {
if(a[x]) change(x, -1), change(x+n, -1);
else change(x, 1), change(x+n, 1);
a[x] = !a[x];
a[x+n] = !a[x+n];
}
}
}
return 0;
}
还不懂的，下面还有一种代码。有注释！
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,c[1000010];
bool a[1000010];//2*n，所以数组大小也要乘二
int lowbit(int x){
return x&-x;
}
void add(int x,int k){
while(x<=2*n){
c[x]+=k;
x+=lowbit(x);
}
}
int sum(int x){
int ans=0;
while(x>0){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
int main(){
int t,x,y,order;
scanf("%d",&t);
while(t--){
int m;
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
for(int i=1;i<=2*n+1;i++){
add(i,1);//一开始路都是好的
a[i]=1;//一开始是连通的
}
while(m--){
scanf("%d%d",&order,&x);
if(order==1){
scanf("%d",&y);
if(x>y){
swap(x,y);//看下面的s1和s2（不然减不了，要大的在后面）
}
int s1=sum(y-1)-sum(x-1);//y-1到 x 之间所有数的和（有路就是1，没有就是0）
int s2=sum(x+n-1)-sum(y-1);// x+n-1 到 y 之间数的和（从n那边绕过来，因为1和n相邻，所以需要这一行）
if(s1==y-x||s2==x+n-y){
//如果连通（有路就是1，没有就是0，所以才会相等）
printf("1\n");
}else{
printf("0\n");
}
}else{
if(a[x]){
//如果路是好的
add(x,-1);
add(x+n,-1);//炸掉！！！
}else{
add(x,1);
add(x+n,1);//修好
}
a[x]=!a[x];//取反码
a[x+n]=!a[x+n];
}
}
}
return 0;
}
区间修改，单点查询
这看起来与单点修改&区间查询差不多，但实际上有很大的区别。
如果我们按照原来的效率，得到的就是 O(n q) ，稳炸。
突破口：差分
思考一下，如果区间修改2到4位之后求第3位，我们就可以加上修改的数。而如果求第5位，我们只需要在第3位的基础上减去修改的数就可以了。举个例子：在数组第2位和第4位之间加上2，只需要将数组从0 0 0 0 0变成0 2 0 0 -2即可。当询问第3位时，答案就是输入的3的值+0+2+0即可。当询问5时，答案就是输入的5的值+0+2+0+0+-2=输入的5的值+0。这就是解法了！
部分代码
void add(ll s,ll num)
{
chafen[s]+=num; //修改得到x,y,s时,只需要求add(x,s)和add(y,-s)
}
如何让它再快一些呢？如果我们将我们刚刚打出来的树状数组来维护差分的这个数组，效率就达到最高啦~
void add(ll s,ll num)
{
for(ll i=s;i<=n;i+=lowbit(i)) tree[i]+=num;//树状数组维护差分修改
}
最后
那么，你学会了吗？
还不会的话评论区@我，包会！
还有……
记得给个小虹心！
