差分思想+树状数组

　　我们知道，基础的树状数组只能方便进行单点修改，若要进行区间修改，则树状数组就会有其劣势。所以，我们引入差分思想，来方便进行区间修改(毕竟树状数组还是比线段树好打得多QAQ)
　　何为差分呢？
　　现在我们有一个从小到大的数列a[]
　　a 1 3 6 8 9
　　然后还有一个差分数组b[]
　　b 1 2 3 2 1
　　相信某些小伙伴已经看出端倪了..这里b[i]=a[i]-a[i-1]，我令a[0]=0，故b[1]=a[1]。
　　拥有了b数组，我们就可以很简单的求出bit[]中任意一个数，只需bit[i]=sigma(k=1 to i) b[k]（这个很好推吧..）
　　我觉得现在该有人说我zz了..何必不直接查询a[i]而是找这么麻烦一个方法..这里我们转回正题！别忘了，题目要我们进行区间修改..
　　我们知道，树状数组对于单点值的修改十分方便（不懂的去看树状数组1），对于区间的修改就比较尴尬..而我们又不想敲死长的线段树..怎么办呢，这时候差分就显出优势
　　还是上面的a[]和b[]，现在我们使区间[2,4]的所有数均+2，则a[]/b[]变为
　　a 1 5 8 10 9
　　b 1 4 3 2 -1
　　事实上，这里只有b[2]和b[5]发生了变化，因为区间内元素均增加了同一个值，所以b[3]，b[4]是不会变化的。
　　这里我们就有了第二个式子：对于区间[x,y]的修改（增加值为d）在b数组内引起变化的只有 b[x]+=d，b[y+1]-=d。（这个也很好推的..）
　　这样，我们就把树状数组的软肋用差分解决了

下面来看两个题目：

洛谷3368

链接：https://www.luogu.org/problem/show?pid=3368

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=500000+10;
 6 int c[maxn];
 7 int n,m;
 8 int lowbit(int x){
 9     return x&(-x);
10 }
11 void add(int x,int d){
12     while(x<=n){
13         c[x]+=d;
14         x+=lowbit(x);
15     }
16 }
17 int sum(int x){
18     int ret=0;
19     while(x>0){
20         ret+=c[x];
21         x-=lowbit(x);
22     }
23     return ret;
24 }
25 int main(int argc, char const *argv[])
26 {
27     /* code */
28     memset(c,0,sizeof(c));
29     scanf("%d%d",&n,&m);
30     int last=0;
31     for(int i=1;i<=n;i++){
32         int x;
33         scanf("%d",&x);
34         add(i,x-last);
35         last=x;
36     }
37     while(m--){
38         int num;
39         scanf("%d",&num);
40         if(num==1){
41             int x,y,k;
42             scanf("%d%d%d",&x,&y,&k);
43             add(x,k);
44             add(y+1,-k);
45         }else{
46             int r;
47             scanf("%d",&r);
48             printf("%d
",sum(r));
49         }
50     }
51     return 0;
52 }

View Code

qscoj16

链接：http://qscoj.cn/problem/16/

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 using namespace std;
 6 const int maxn=100000+10;
 7 long long c[maxn];
 8 int n,m;
 9 int lowbit(int x){
10     return x&(-x);
11 }
12 void add(int x,long long d){
13     while(x<=n){
14         c[x]+=d;
15         x+=lowbit(x);
16     }
17 }
18 long long sum(int x){
19     long long ret=0;
20     while(x>0){
21         ret+=c[x];
22         x-=lowbit(x);
23     }
24     return ret;
25 }
26 int main(int argc, char const *argv[])
27 {
28     /* code */
29     scanf("%d%d",&n,&m);
30     memset(c,0,sizeof(c));
31     long long last=0;
32     for(int i=1;i<=n;i++){
33         long long x;
34         scanf("%lld",&x);
35         add(i,x-last);
36         last=x;
37     }
38     while(m--){
39         long long l,r,k;
40         scanf("%lld%lld%lld",&l,&r,&k);
41         add(l,k);
42         add(r+1,-k);
43     }
44     for(int i=1;i<=n;i++)
45     printf("%lld ",sum(i));
46     printf("
");
47     return 0;
48 }

View Code