分块
分块特点：一种优雅的暴力，大段维护，小段朴素。
假设我们有一个长度为 \(n\) 的数组 \(a\)。
需要我们维护区间修改和区间查询等操作。
那么朴素算法就不用说了，如果是万能的线段树还行。但是线段树码量过大，容易出bug。
这个时候就得用到分块的思想。
分块思想：
对于需要维护的数组 \(a\)，将其分为 \(num\) 块，每一块块长为 \(block\)，然后对每一块进行维护，最后求解。
那么这个 \(block\) 是多少好呢？
根据均值不等式，当 \(\frac{n}{block}=block\)，即当 \(block=\sqrt{n}\) 时最优，单次修改为 \(O(\sqrt{n})\)。
显然有些情况下，\(n\mod block \neq 0\)，即分完会有剩下的元素。那么很显然可以将块数 \(+1\)，就当作是新建一块。
对于每个块的维护
可以建立一个结构体来存放每一个快。
内存块的左端点、右端点、区间和。如果题目中有区间修改，那么类似的，放一个懒标记进去，表示该区间所有数都要加上多少。
对于第 \(i\) 块 \((\forall\ 1\le i\le num)\)：
左端点 \(=(i-1)\lfloor{\sqrt{n}}\rfloor+1\)，右端点是 \(\min (i\lfloor{\sqrt{n}}\rfloor,n)\)。因为有可能 \(n\mod block \neq 0\)。
下面就是一个例子：
其中：
\[(1\le i \le n)\\ l_i=\left\{1,5,9,13,17\right\}\\ r_i=\left\{4,8,12,16,17\right\}\]
对于每个下标 \(i\)，用 \(belong_i\) 表示第 \(i\) 号元素属于第 \(belong_i\) 块。
操作维护
设 \(l,r\) 分别是增加区间的左右端点，增加 \(d\)。
若 \(belong_l=belong_r\)，即在同一个块中：
将所有的 \(a_i\) 加上 \(d\)，再将 \(sum_i\leftarrow sum_i+d(r-l+1)\)。（小段朴素）
否则，设 \(belong_l=q,belong_r=p\)：
对于区间 \(\)，用同一个块中的方法进行维护。
即维护下图的区间 \(\)。
同理，也可以维护区间 \(\)，即上图区间 \(\)。
现在我们已经解决了区间 \(\) 和 \(\)，还剩下在两个区间中间的区间 \(\) 和 \(\)。
显然 \(\) 和 \(\) 是两个块，就将块的懒标记全部加上 \(d\) 即可。
若不用懒标记，像小区间那样的朴素维护，很容易时间就超了。
代码部分
例题：P3374 【模板】树状数组 1。
一个块的元素：
struct NODE{ ljl l,r,sum; }node;建立块：
void build() { block=floor(sqrt(n)); num=n/block; if(n%block!=0) ++num;//不能分为整块 for(ljl i=1;i<=num;++i) { node.l=(i-1)*block+1,node.r=min(i*block,n);//公式已说 for(ljl j=node.l;j<=node.r;++j) node.sum+=a; }// for(ljl i=1;i<=num;++i)// cout<<node.l<<' '<<node.r<<" "<<node.sum<<'\n'; for(ljl i=1;i<=n;++i) belong=(i-1)/block+1; return; }单点修改：
void update(ljl x,ljl y) { a+=y; node].sum+=y; return; }区间查询：
ljl query(ljl l,ljl r) { ljl q=belong,p=belong; if(q==p) { ljl ans=0; for(ljl i=l;i<=r;++i) ans+=a; return ans; } ljl ans=0; for(ljl i=l;i<=node.r;++i) ans+=a; for(ljl i=q+1;i<=p-1;++i) ans+=node.sum; for(ljl i=node.l;i<=r;++i) ans+=a; return ans; }完整代码：
#include<bits/stdc++.h>using namespace std;#define ljl long longconst ljl N=5e5+5;ljl n,m,a,block;namespace BLOCK{ struct NODE{ ljl l,r,sum; }node; ljl belong,num; void build() { block=floor(sqrt(n)); num=n/block; if(n%block!=0) ++num; for(ljl i=1;i<=num;++i) { node.l=(i-1)*block+1,node.r=min(i*block,n); for(ljl j=node.l;j<=node.r;++j) node.sum+=a; }// for(ljl i=1;i<=num;++i)// cout<<node.l<<' '<<node.r<<" "<<node.sum<<'\n'; for(ljl i=1;i<=n;++i) belong=(i-1)/block+1; return; } void update(ljl x,ljl y) { a+=y; node].sum+=y; return; } ljl query(ljl l,ljl r) { ljl q=belong,p=belong; if(q==p) { ljl ans=0; for(ljl i=l;i<=r;++i) ans+=a; return ans; } ljl ans=0; for(ljl i=l;i<=node.r;++i) ans+=a; for(ljl i=q+1;i<=p-1;++i) ans+=node.sum; for(ljl i=node.l;i<=r;++i) ans+=a; return ans; }}using namespace BLOCK;int main(){ ios::sync_with_stdio(0); cin>>n>>m; for(ljl i=1;i<=n;++i) cin>>a; build();// for(ljl i=1;i<=n;++i)// cout<<belong<<' ';// cout<<"\n"; while(m--) { ljl op,x,y; cin>>op>>x>>y; if(op==1) update(x,y); else { cout<<query(x,y)<<'\n'; }// cout<<"--------------\n";// for(ljl i=1;i<=num;++i)// cout<<node.l<<" "<<node.r<<" "<<node.sum<<'\n';// cout<<"----------------\n"; } return 0;}例题二：P3372 【模板】线段树 1。
因为上一题仅仅是单点修改，过于简单。
所以上强度：
本题需要区间修改和区间查询，具体看代码：
#include<bits/stdc++.h>using namespace std;#define ljl long longconst ljl N=1e5+5,BLOCKS=1e3+5;ljl n,a,q,l,r,v;namespace BLOCK{ struct NODE{ ljl l,r,sum,lz; }node; ljl belong,num,block; void build()//建块 { block=(ljl)sqrt(n); num=n/block; if(n%block)++num; for(ljl i=1;i<=num;++i) { node.l=(i-1)*block+1,node.r=min(i*block,n); for(ljl j=node.l;j<=node.r;++j) node.sum+=a; } for(ljl i=1;i<=n;++i) belong=(i-1)/block+1; return; } void change_part(ljl id,ljl l,ljl r)//对于是一个块内的区间修改 { for(ljl i=l;i<=r;++i) a+=v; node.sum+=v*(r-l+1); } void change(ljl l,ljl r)//询问的区间修改 { ljl q=belong,p=belong; if(q==p) { change_part(q,l,r);return; } change_part(q,l,node.r);//按照上文讲过的方法实现即可 change_part(p,node.l,r); for(ljl i=q+1;i<p;++i) node.lz+=v;//这里是懒标记 return; } ljl query_part(ljl id,ljl l,ljl r) { ljl ans=0; for(ljl i=l;i<=r;++i) ans=ans+(a+node.lz); return ans; } ljl query(ljl l,ljl r) { ljl q=belong,p=belong; if(q==p) return query_part(q,l,r); ljl ans=0; ans+=query_part(q,l,node.r); ans+=query_part(p,node.l,r); for(ljl i=q+1;i<p;++i) ans=ans+node.sum+(node.r-node.l+1)*node.lz; return ans; }}using namespace BLOCK;int main(){ ios::sync_with_stdio(0); cin>>n>>q; for(ljl i=1;i<=n;++i) cin>>a; build(); while(q--) { ljl op; cin>>op; if(op==1) { cin>>l>>r>>v; change(l,r); } else { cin>>l>>r; cout<<query(l,r)<<'\n'; } } return 0;}线段树和分块的比较：
线段树1：
时间空间代码长度分块974ms1.98MB1.48KB线段树297ms11.19MB1.67KB树状数组1：
时间空间代码长度分块1.34s9.55MB1.40KB树状数组521ms4.23MB554B虽然分块不如线段树或树状数组，但是在不熟练他们俩的情况下可以使用分块，反正能A。
页:
[1]