分块简介
分块的基本思想是通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。
如何分块
一般的，我们会把原数组分成块长为 \(\sqrt{n}\) 的几段，初始化的复杂度为 \(O(n)\) ，单次操作的复杂度是 \(O(\sqrt{n})\)
参考题目可以发现，出题人貌似想让我们写线段树，于是我们考虑如何不写线段树，我们可以采用分块。
关于变量的一些定义：
\(block\) ：块长
\(tot\) ：总块数
\(L_i\) ：第 \(i\) 块的左端点
\(R_i\) ：第 \(i\) 块的右端点
\(pos_i\) ：第 \(i\) 个数在所在的块的编号
\(s_i\) ：第 \(i\) 块所有数字的和
\(tag_i\) ：第 \(i\) 块的加法标记，具体作用见下文
初始化：
首先我们定义块长为 \(\sqrt{n}\)
枚举每一个块，它的左端点就是上一块右端点的下一个元素，右端点就是 \(\min(i*block,n)\)
接下来枚举这个区块内的所有元素，用 \(s_i\) 记录总和，同时把这些元素的 \(pos\) 标记为这个块的编号
因为我们只遍历了一整个序列，所以预处理的复杂度是 \(O(n)\) 的
初始化部分代码
inline void build() {
block=sqrt(n);
while(++tot) {
L[tot]=R[tot-1]+1;
R[tot]=min(block*tot,n);
for(int i=L[tot];i<=R[tot];++i)
pos[i]=tot,s[tot]+=a[i];
if(R[tot]==n)
break;
}
}
区间加法
我们要将 \(a_x \sim a_y\) 加上 \(val\) ，暴力复杂度显然是 \(O(n)\) ，考虑优化
如果 \(x,y\) 在同一个块，显然暴力加的复杂度不会超过 \(O(\sqrt{n})\) ，直接暴力即可
如果 \(x,y\) 不在同一个块，我们可以把这个块分成两边的零散块与中间的整块分别处理
旁边的零散块直接暴力处理
对于中间的整块，更新每一个加法标记 \(tag\) ，同时更新这个块的和 \(s\) 即可
由于块长为 \(O(\sqrt{n})\) ，零散块的操作复杂度不会超过 \(O(2 \times \sqrt{n})\) ，整块的数量不会超过 \(\sqrt{n}\)
所以这一部分的复杂度为 \(O(sqrt{n})\)
区间加法代码：
inline void Plus(int x,int y,int val) {
int l=pos[x],r=pos[y];
if(l==r) { // 判断是否在同一块内
for(int i=x;i<=y;++i)
a[i]+=val,s[l]+=val; // 暴力加
}
else {
for(int i=x;i<=R[l];++i)
a[i]+=val,s[l]+=val; // 处理左边的零散块
for(int i=l+1;i<=r-1;++i)
tag[i]+=val,s[i]+=val*(R[i]-L[i]+1); // 处理中间的整块
for(int i=L[r];i<=y;++i)
a[i]+=val,s[r]+=val; // 处理右边的零散块
}
}
区间查询
查询 \(\sum^{y}_{i=x}a_i\)
如果 \(x,y\) 在同一个块，显然暴力查询的复杂度不会超过 \(O(\sqrt{n})\) ，注意不要忘记加上加法标记
如果 \(x,y\) 不在同一个块，我们两边的零散块同样暴力处理，中间的整块直接累计和即可
同样，这一部分的时间复杂度为 \(O(\sqrt{n})\)
区间查询代码：
inline int query(int x,int y) {
int l=pos[x],r=pos[y];
int ans=0;
if(l==r) { // 判断是否在同一块内
for(int i=x;i<=y;++i)
ans+=a[i]+tag[l]; // 暴力加
}
else {
for(int i=x;i<=R[l];++i)
ans+=a[i]+tag[l]; // 处理左边的零散块
for(int i=l+1;i<=r-1;++i)
ans+=s[i]; // 处理中间的整块(每一个整块的和都加上过tag)
for(int i=L[r];i<=y;++i)
ans+=a[i]+tag[r]; // 处理右边的零散块
}
return ans;
}
将以上代码结合起来，我们就可以用分块 AC 本题
完整代码：
#include <cmath>
#include <cstdio>
#define min(a,b) ((a)<(b)?(a):(b))
typedef long long ll;
using namespace std;
const int N=1e5+7;
ll a[N];
ll s[N],tag[N];
int L[N],R[N],pos[N];
int n,m,block,tot;
inline void build() {
block=sqrt(n);
while(++tot) {
L[tot]=R[tot-1]+1;
R[tot]=min(block*tot,n);
for(int i=L[tot];i<=R[tot];++i)
pos[i]=tot,s[tot]+=a[i];
if(R[tot]==n)
break;
}
}
inline void Plus(int x,int y,ll val) {
int l=pos[x],r=pos[y];
if(l==r) { // 判断是否在同一块内
for(int i=x;i<=y;++i)
a[i]+=val,s[l]+=val; // 暴力加
}
else {
for(int i=x;i<=R[l];++i)
a[i]+=val,s[l]+=val; // 处理左边的零散块
for(int i=l+1;i<=r-1;++i)
tag[i]+=val,s[i]+=val*(R[i]-L[i]+1); // 处理中间的整块
for(int i=L[r];i<=y;++i)
a[i]+=val,s[r]+=val; // 处理右边的零散块
}
}
inline ll query(int x,int y) {
int l=pos[x],r=pos[y];
ll ans=0;
if(l==r) { // 判断是否在同一块内
for(int i=x;i<=y;++i)
ans+=a[i]+tag[l]; // 暴力加
}
else {
for(int i=x;i<=R[l];++i)
ans+=a[i]+tag[l]; // 处理左边的零散块
for(int i=l+1;i<=r-1;++i)
ans+=s[i]; // 处理中间的整块(每一个整块的和都加上过tag)
for(int i=L[r];i<=y;++i)
ans+=a[i]+tag[r]; // 处理右边的零散块
}
return ans;
}
signed main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%lld",a+i);
build();
for(int op,l,r;m;--m) {
scanf("%d%d%d",&op,&l,&r);
if(op==1) {
ll k;
scanf("%lld",&k);
Plus(l,r,k);
}
else
printf("%lld\n",query(l,r));
}
return 0;
}
习题
与例题思想相近，稍加修改即可AC
P2846 [USACO08NOV]Light Switching G
区间异或，将模板稍微改一下就行，还可以收获5倍经验
区间开方与求和
求和直接用分块即可，那么怎么进行区间开方呢
注意到一个性质，一个数一直开方后总会变成 \(1\) 或 \(0\)
所以我们一开始先暴力开方，如果一段区间内所有的数都是 \(1\) 或 \(0\) ，那么这段区间不管怎么开方，它的每一个数都不会被改变，所以在修改时这段区间直接跳过就行
代码：
#include <cmath>
#include <cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
typedef long long ll;
using namespace std;
const int N=1e5+7;
ll a[N];
ll s[N];
int L[N],R[N],pos[N];
bool vis[N];
int n,m;
int block,tot;
inline void build() {
block=sqrt(n);
while(++tot) {
L[tot]=R[tot-1]+1;
R[tot]=min(n,block*tot);
for(int i=L[tot];i<=R[tot];++i)
pos[i]=tot,s[tot]+=a[i];
if(R[tot]==n)
break;
}
}
inline void check(ll x) { // 判断这个块是否全为1或0
if(vis[x])
return ;
for(int i=L[x];i<=R[x];++i)
if(a[i]>1)
return ;
vis[x]=true;
}
inline void update(int x,int y) {
int l=pos[x],r=pos[y];
ll t;
if(l==r) {
if(!vis[l]) {
for(int i=x;i<=y;++i) {
s[l]-=a[i]-floor(sqrt(a[i]));
a[i]=sqrt(a[i]);
}
check(l);
}
}
else {
for(int i=x;i<=R[l];++i) {
s[l]-=a[i]-floor(sqrt(a[i]));
a[i]=sqrt(a[i]);
}
check(l);
for(int i=l+1;i<r;++i)
if(!vis[i]) {
for(int j=L[i];j<=R[i];++j) {
s[i]-=a[j]-floor(sqrt(a[j]));
a[j]=sqrt(a[j]);
}
check(i);
}
for(int i=L[r];i<=y;++i) {
s[r]-=a[i]-floor(sqrt(a[i]));
a[i]=sqrt(a[i]);
}
check(r);
}
}
inline ll query(int x,int y) {
int l=pos[x],r=pos[y];
ll ans=0;
if(l==r) {
for(int i=x;i<=y;++i)
ans+=a[i];
}
else {
for(int i=x;i<=R[l];++i)
ans+=a[i];
for(int i=l+1;i<r;++i)
ans+=s[i];
for(int i=L[r];i<=y;++i)
ans+=a[i];
}
return ans;
}
signed main() {
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lld",a+i);
build();
scanf("%d",&m);
for(int op,l,r;m;--m) {
scanf("%d%d%d",&op,&l,&r);
if(op)
printf("%lld\n",query(min(l,r),max(l,r)));
else
update(min(l,r),max(l,r));
}
return 0;
}