题解：P13976 数列分块入门 1
Aventurine_
·
·
题解
分块模板题之单点查询
在这里介绍一下分块算法。在学习分块前最好先学会线段树，然后你就能体会到分块的妙处。
区间查询版 P13979
分块是什么
分块是一种“优雅的暴力”，它的代码比线段树和树状数组简单且易理解，又比暴力效率高，能以 O(m\sqrt{n}) 的时间复杂度解决一些区间修改及区间查询问题。具体思路是将长度为 n 的序列分为 t 块，每块长度为 n/t。对于每个区间，如果包含了整块，就对整块操作；不是整块的部分就直接暴力枚举操作。
分块操作
分块的一些基本要素如下。
- 块的大小用 len 表示，len=n/t。
- 块的数量用 t 表示。
- 每个块的左右边界。定义数组 st，ed 分别表示每个块的开头和末尾元素的位置，则有 st_i=(i-1)\times len+1,ed_i=i\times len。
- 每个元素所属的块。定义数组 pos，pos_i 表示第 i 个元素所在的块，则有 pos_i=(i-1)/len+1。
具体代码
int len=sqrt(n);//len表示块的大小
int t=n/len; // t表示块数
if(n%len)t++; //如果结尾不满一块
for(int i=1;i<=t;i++)//确定每个块开头结尾
{
st[i]=(i-1)*len+1;
ed[i]=i*len;
}
ed[t]=n;
for(int i=1;i<=n;i++)
{
pos[i]=(i-1)/len+1;//确定pos
}
本题实现
对于本题的区间加操作，我们定义数组 add 表示每一块的增量标记（类似于线段树的 lazytag 标记），初始值为 0。
接下来是处理区间修改与区间查询，原则是“整块整体维护，碎片暴力枚举”。区间操作分为两种情况。
第一种情况
#### 第二种情况
$[L,R]$ 不在同一块内，此时对于被完全包含的块 $i$，使 $add_i=add_i+d$。对于两头的碎片，按照第一种情况处理即可。
##### 具体代码
>```
> int p=pos[l],q=pos[r];
> if(p==q)//如果被包含在一个块里
> {
> for(int i=l;i<=r;i++)a[i]+=d;//暴力加
> }
> else//不被包含在一个块里
> {
> for(int i=p+1;i<=q-1;i++)add[i]+=d;//整块加
>
> for(int i=l;i<=ed[p];i++)a[i]+=d;//开头散块
>
> for(int i=st[q];i<=r;i++)a[i]+=d;//结尾散块
> }
>```
* * *
对于查询操作，就很简单了，只需要将此点的 $a_i$ 与它所属的块的 $add$ 值加起来即可。
##### 具体代码
>```
> int q=pos[r];
> int ans=0;
> ans=a[r]+add[q];
> return ans;
>```
## 复杂度分析
将 $len$ 取 $\sqrt{n}$ 时，$t$ 也约为 $\sqrt{n}$，分析代码可知，修改无论是处理碎片还是整块，时间复杂度都为 $O(\sqrt{n})$，查询只需要 $O(1)$，共有 $m$ 次询问，总复杂度为 $O(m\sqrt{n})$。
## 完整代码
这就是本题的代码实现了，下面是完整代码。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+15;
int n,m;
int a[N];
int st[N],ed[N],pos[N];//st表示每个块的开头，ed表示结尾，pos表示每个元素属于那个块
int add[N];//sum是总和，add是加数的标记
void change(int l,int r,int d)//区间修改
{
int p=pos[l],q=pos[r];
if(p==q)//如果被包含在一个块里
{
for(int i=l;i<=r;i++)a[i]+=d;//暴力加
}
else//不被包含在一个块里
{
for(int i=p+1;i<=q-1;i++)add[i]+=d;//整块加
for(int i=l;i<=ed[p];i++)a[i]+=d;//开头散块
for(int i=st[q];i<=r;i++)a[i]+=d;//结尾散块
}
}
int query(int r)
{
int q=pos[r];
int ans=0;
ans=a[r]+add[q];
return ans;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
//----------------------分块
int len=sqrt(n);//len表示块的大小
int t=n/len; // t表示块数
if(n%len)t++; //如果结尾不满一块
for(int i=1;i<=t;i++)//确定每个块开头结尾
{
st[i]=(i-1)*len+1;
ed[i]=i*len;
}
ed[t]=n;
for(int i=1;i<=n;i++)
{
pos[i]=(i-1)/len+1;//确定pos
}
//————————————操作
m=n;
while(m--)
{
int o,x,y,k;
cin>>o>>x>>y>>k;
if(o==0)
{
change(x,y,k);
}
else
{
cout<<query(y)<<endl;
}
}
return 0;
}
```