分块之区间修改与单点查询
2018-06-18 04:03:08来源:未知 阅读 ()
给出一个长为n的数列,以及n个操作,操作涉及区间加法,单点查值。
这是一道能用许多数据结构优化的经典题,可以用于不同数据结构训练。
数列分块就是把数列中每m个元素打包起来,达到优化算法的目的。
以此题为例,如果我们把每m个元素分为一块,共有n/m块,每次区间加的操作会涉及O(n/m)个整块,以及区间两侧两个不完整的块中至多2m个元素。
我们给每个块设置一个加法标记(就是记录这个块中元素一起加了多少),每次操作对每个整块直接O(1)标记,而不完整的块由于元素比较少,暴力修改元素的值。
每次询问时返回元素的值加上其所在块的加法标记。
这样每次操作的复杂度是O(n/m)+O(m),根据均值不等式,当m取√n时总复杂度最低,为了方便,我们都默认下文的分块大小为√n。
区间加法
1 void interval_add(int ll,int rr,int v) 2 { 3 for(int i=ll;i<=min(where[ll]*m,rr);i++) 4 //这里判断的是where[ll]是不完全块的情况,也就是ll在他实际块最左端的右侧, 5 // 然后便利ll-所在块的结尾/rr,暴力增加 6 a[i]+=v; 7 if(where[ll]!=where[rr]) 8 // 注意如果是ll和rr在一个块中的话,上面已经加过一边,所以不用加 9 { 10 for(int i=(where[rr]-1)*m;i<=rr;i++) 11 // 这里判断的是rr在他实际所在块的最右端左侧的情况 12 // where[i]*m表示的是第i个块最右端的元素 13 // where[rr]-1就是rr所在块左边那个块最右端的元素 14 // 一直到rr暴力增加 15 a[i]+=v; 16 } 17 for(int i=where[ll]+1;i<=where[rr]-1;i++) 18 //这里where[ll]和where[rr]均已暴力处理过,所以只枚举中间的块就可以 19 add[i]+=v; 20 }
单点查询
1 printf("%d\n",a[v]+add[where[v]]);
完整代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=100001; 7 int n,q,m,how,l,r,v; 8 int a[MAXN];// 初始值 9 int add[MAXN];// 后来每个块上加入的值 10 int where[MAXN];// 记录每一个值对应第几块 11 void interval_add(int ll,int rr,int v) 12 { 13 for(int i=ll;i<=min(where[ll]*m,rr);i++) 14 //这里判断的是where[ll]是不完全块的情况,也就是ll在他实际块最左端的右侧, 15 // 然后便利ll-所在块的结尾/rr,暴力增加 16 a[i]+=v; 17 if(where[ll]!=where[rr]) 18 // 注意如果是ll和rr在一个块中的话,上面已经加过一边,所以不用加 19 { 20 for(int i=(where[rr]-1)*m;i<=rr;i++) 21 // 这里判断的是rr在他实际所在块的最右端左侧的情况 22 // where[i]*m表示的是第i个块最右端的元素 23 // where[rr]-1就是rr所在块左边那个块最右端的元素 24 // 一直到rr暴力增加 25 a[i]+=v; 26 } 27 for(int i=where[ll]+1;i<=where[rr]-1;i++) 28 //这里where[ll]和where[rr]均已暴力处理过,所以只枚举中间的块就可以 29 add[i]+=v; 30 } 31 int main() 32 { 33 scanf("%d",&n); 34 m=sqrt(n); 35 for(int i=1;i<=n;i++) 36 scanf("%d",&a[i]); 37 for(int i=1;i<=n;i++) 38 where[i]=(i-1)/m+1;// 这里的i可以-1(hzwer写的是-1)也可以不写,不写的话第一块的元素个数会是m-1 39 scanf("%d",&q); 40 for(int i=1;i<=q;i++) 41 { 42 scanf("%d",&how); 43 if(how==1)// 区间加 44 { 45 scanf("%d%d%d",&l,&r,&v); 46 interval_add(l,r,v); 47 } 48 else// 单点查询 49 { 50 scanf("%d",&v); 51 printf("%d\n",a[v]+add[where[v]]); 52 // where保存的是这个点所属的块,add表示这个块已经增加的元素 53 //a[v]是这个点开始的值,一加就是答案 54 } 55 } 56 return 0; 57 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【题解】P1440 求m区间内的最小值 2019-12-23
- c++实现文件复制并修改相应属性 2019-12-14
- 最新修改Oracle10gscott用户 2019-11-21
- 自定义日历(四)-区间选择控件 2019-11-02
- 【学习笔记】RMQ-Range Minimum/Maximum Query (区间最小/ 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash