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

给出一个长为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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏图形学与OpenGL

实验4 类初步

 注:本次实验有可能会安排在校内http://acm.hpu.edu.cn/contest.php进行。

892
来自专栏小樱的经验随笔

HUST 1541 Student’s question

1541 - Student’s question 时间限制:1秒 内存限制:128兆 696 次提交 134 次通过 题目描述 YYis a stude...

3518
来自专栏决胜机器学习

PHP数据结构(十五) ——哈希表​

PHP数据结构(十五)——哈希表 (原创内容,转载请注明来源,谢谢) 一、概述 查找的效率与查找的次数有关,查找的次数越少速度越快。因此,希望能够一次查找出结...

4619
来自专栏田云专栏

virtualdom diff算法实现分析

这两个月接触下vue ,花了两天时间了解了下vue的virtualdom实现,记录下学习心得。

3656
来自专栏互联网技术杂谈

快速熟悉Java

参考著名的python快速入门(Quick Python Script Explanation for Programmers):https://mp.weix...

2779
来自专栏数据结构与算法

10:大整数加法

10:大整数加法 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 求两个不超过200位的非负整数的和。 输入有两行,每...

47812
来自专栏数据结构与算法

LOJ#6282. 数列分块入门 6

内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论测试数据 题目描述 给出...

2667
来自专栏章鱼的慢慢技术路

排序算法的实现与比较

1768
来自专栏田云专栏

virtualdom diff算法实现分析

这两个月接触下vue ,花了两天时间了解了下vue的virtualdom实现,记录下学习心得。

6975
来自专栏calmound

uva Andy's First Dictionary

题目很简单,数组开大就好,5000但加上重复就不够了10000都小,sort排序前闭合后开,对二维字符窜排序用结构体,所以只有一组的时候只是本身但是不会出现RE...

3474

扫码关注云+社区

领取腾讯云代金券