首页 > > 程序设计 > C/C++ >

分块之区间查询与区间修改

2018-06-17 22:34:32来源：未知阅读 ()

给出一个长为n的数列，以及n个操作，操作涉及区间加法，区间求和。

这题的询问变成了区间上的询问，不完整的块还是暴力；而要想快速统计完整块的答案，需要维护每个块的元素和，先要预处理一下。

考虑区间修改操作，不完整的块直接改，顺便更新块的元素和；完整的块类似之前标记的做法，直接根据块的元素和所加的值计算元素和的增量。

更改后的区间加法

 1 void interval_add(LL ll,LL rr,LL v)
 2 {
 3     for(LL i=ll;i<=min(where[ll]*m,rr);i++)
 4     //这里判断的是where[ll]是不完全块的情况，也就是ll在他实际块最左端的右侧，
 5     // 然后便利ll-所在块的结尾/rr，暴力增加 
 6         a[i]+=v,sum[where[ll]]+=v;
 7         // 注意sum表示的是一个块内的元素和，where表示的是块的位置 
 8     if(where[ll]!=where[rr])
 9     // 注意如果是ll和rr在一个块中的话，上面已经加过一边，所以不用加 
10     {
11         for(LL i=(where[rr]-1)*m+1;i<=rr;i++)
12         // 这里判断的是rr在他实际所在块的最右端左侧的情况
13         // where[i]*m表示的是第i个块最右端的元素
14         // where[rr]-1就是rr所在块左边那个块最右端的元素
15         // 一直到rr暴力增加 
16             a[i]+=v,sum[where[rr]]+=v;
17     }    
18     for(LL i=where[ll]+1;i<=where[rr]-1;i++)
19     //这里where[ll]和where[rr]均已暴力处理过，所以只枚举中间的块就可以 
20         add[i]+=v;
21 }

区间查询

 1 void interval_ask(LL ll,LL rr)
 2 {
 3     LL ans=0;
 4     for(LL i=ll;i<=min(where[ll]*m,rr);i++)
 5         ans+=a[i]+add[where[i]];
 6         // 暴力求和 ,注意where里面要写ll\i，因为我们始终是在ll到它的所在区间结尾的元素内循环 
 7         // 
 8     if(where[ll]!=where[rr])
 9         for(LL i=(where[rr]-1)*m+1;i<=rr;i++)
10         //注意这里需要加一，因为所有的for都是<=，如果不写+1会加两边 
11             ans+=a[i]+add[where[i]];
12             
13     for(LL i=where[ll]+1;i<=where[rr]-1;i++)
14         ans+=sum[i]+add[i]*m;
15         // 这里要*区间内元素的个数 
16         
17     printf("%lld\n",ans);
18 }

完整代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define LL long long 
 6 using namespace std;
 7 const LL MAXN=100001;
 8 LL n,q,m,how,l,r,v;
 9 LL a[MAXN];// 初始值
10 LL add[MAXN];// 后来每个块上加入的值
11 LL where[MAXN];// 记录每一个值对应第几块
12 LL sum[MAXN];//记录每一块内的元素和 
13 void interval_add(LL ll,LL rr,LL v)
14 {
15     for(LL i=ll;i<=min(where[ll]*m,rr);i++)
16     //这里判断的是where[ll]是不完全块的情况，也就是ll在他实际块最左端的右侧，
17     // 然后便利ll-所在块的结尾/rr，暴力增加 
18         a[i]+=v,sum[where[ll]]+=v;
19         // 注意sum表示的是一个块内的元素和，where表示的是块的位置 
20     if(where[ll]!=where[rr])
21     // 注意如果是ll和rr在一个块中的话，上面已经加过一边，所以不用加 
22     {
23         for(LL i=(where[rr]-1)*m+1;i<=rr;i++)
24         // 这里判断的是rr在他实际所在块的最右端左侧的情况
25         // where[i]*m表示的是第i个块最右端的元素
26         // where[rr]-1就是rr所在块左边那个块最右端的元素
27         // 一直到rr暴力增加 
28             a[i]+=v,sum[where[rr]]+=v;
29     }    
30     for(LL i=where[ll]+1;i<=where[rr]-1;i++)
31     //这里where[ll]和where[rr]均已暴力处理过，所以只枚举中间的块就可以 
32         add[i]+=v;
33 } 
34 void interval_ask(LL ll,LL rr)
35 {
36     LL ans=0;
37     for(LL i=ll;i<=min(where[ll]*m,rr);i++)
38         ans+=a[i]+add[where[i]];
39         // 暴力求和 ,注意where里面要写ll，因为我们始终是在ll到它的所在区间结尾的元素内循环 
40         
41     if(where[ll]!=where[rr])
42         for(LL i=(where[rr]-1)*m+1;i<=rr;i++)
43         //注意这里需要加一，因为所有的for都是<=，如果不写+1会加两边 
44             ans+=a[i]+add[where[i]];
45             
46     for(LL i=where[ll]+1;i<=where[rr]-1;i++)
47         ans+=sum[i]+add[i]*m;
48         
49     printf("%lld\n",ans);
50 }
51 int main()
52 {
53     scanf("%lld",&n);
54     scanf("%lld",&q);
55     m=sqrt(n);
56     for(LL i=1;i<=n;i++)
57         scanf("%lld",&a[i]); 
58     for(LL i=1;i<=n;i++)
59         where[i]=(i-1)/m+1,sum[where[i]]+=a[i];// 这里的i可以-1(hzwer写的是-1)也可以不写，不写的话第一块的元素个数会是m-1 
60     
61     for(LL i=1;i<=q;i++)
62     {
63         scanf("%lld",&how);
64         if(how==1)// 区间加
65         {
66             scanf("%lld%lld%lld",&l,&r,&v);
67             interval_add(l,r,v);
68         }
69         else// 单点查询 
70         {
71             scanf("%lld%lld",&l,&r);
72             interval_ask(l,r);
73             // where保存的是这个点所属的块，add表示这个块已经增加的元素
74             //a[v]是这个点开始的值，一加就是答案 
75         } 
76     }
77     return 0;
78 }