树状数组：

区域改值，找单点数据

区域改值涉及到差分数组：

a 1  2  3  4  5  6  7  8  9

1~5 +3

b 3  0  0  -3 0  0  0  0  0

2~8 -1

b 3  -1 0  -3 0  0  0  0  1

求a[6]的新值

a[6]+sum(b[1]~b[6])

设立a数组的差分数组b

用树状数组维护b

   1、可以控制b[l]+k,b[r+1]-k

   2、sum(b[1]~b[6])即树状数组前缀和

校门外的树：1537

输入：

5 4

1 1 3

2 2 5

1 2 4

2 3 5

输出：

1

2

#include <bits/stdc++.h>

using namespace std;

int n,m,k,l,r;

int a[50050];

int b[50050];

int getsum(int x,int y){

   int ans=0;

   int sum[50050]={};

   for(int i=1;i<=y;i++) sum[i]=b[i]+sum[i-1];

   for(int i=x;i<=y;i++) ans=max(ans,sum[i]);

   return ans;

}

int main(){

   cin>>n>>m;

   while(m--){

       cin>>k>>l>>r;

       if(k==1){

           b[l]++;

           b[r+1]--;

           //for(int i=1;i<=n;i++) cout<<b[i]<<" ";cout<<endl;

       }

       else{

           printf("%d\n",getsum(l,r));

       }

   }

   return 0;

}

维护某一段区间的前缀和：树状数组

假设：4～8这段区间新增一棵树

那么：一个标记记录4增加1棵树，一个标记记录8增加1棵树

通过前缀和能统计出来1～8之间一共增加了多少树，也能统计出来1～3增加了多少树

相减就是答案

bl[50050];

br[50050];

cin>>k>>l>>r;

change(l,1);

change(r,1);

ans=sum(r)-sum(l-1);

------

#include <bits/stdc++.h>

using namespace std;

int n,m,k,l,r;

int bl[50050],br[50050];

void change(int x,int g,char c){

   for(int i=x;i<=n;i+=i&-i){

       if(c=='l') bl[i]+=g;

       else br[i]+=g;

   }

}

int getsum(int x,char c){

   int ans=0;

   for(int i=x;i>0;i-=i&-i){

       if(c=='r') ans+=bl[i];

       else ans+=br[i];

   }

   return ans;

}

int main(){

   cin>>n>>m;

   while(m--){

       scanf("%d %d %d",&k,&l,&r);

       if(k==1){

           change(l,1,'l');

           change(r,1,'r');

       }

       else{

           printf("%d\n",getsum(r,'r')-getsum(l-1,'l'));

       }

   }

   return 0;

}

总结：

get(int x)：获取x位置的树状数组值

for(x;x>=1;x-=x&-x) ans+=t[x];

change(int x,int k)：改变x位置的值，变化量为k，连带修改树状数组其他位置的值

for(x;x<=n;x+=x&-x) t[x]+=k;

解决单点修改，修改x：change(x,k);

解决单点查询，求x位置的值：get(x)-get(x-1);

解决单点修改，修改x：change(x,k);

解决区间查询，求l～r位置的值：get(r)-get(l-1);

解决区间修改，这里需要树状数组维护差分数组b，而不是原来的数据数组a：change(l,d);change(r+1,-d);

解决单点查询，求x位置的值：a[x]+get(x);

解决区间修改，区间查询：线段树

三个作业：

1537:用上述差分数组重构

1538:单点修改，区间查询

1539:区间修改，单点查询

三个作业选一个。