分块

Prologue

  • 块:将一个数列分为若干个不相交区间,每一个区间称为块
  • 完整块:进行区间操作时被区间完全覆盖的块
  • 不完整块:进行区间操作时部分被区间覆盖的块 分块是一种个区间进行划分,批量操作,从而降低时间复杂度的数据结构。线段树就是基于分块思想。分块将一个长度为 NN 的区间划分为 N\left \lfloor \sqrt{N} \right \rfloor 个 长度为 N\left \lfloor \sqrt{N} \right \rfloor 和一个长度为 NN2N\left \lfloor \sqrt{N} \right \rfloor^2 的块。分块的思想可以简单概括为:大块维护,局部朴素

初始化

一个块应具有左端点,右端点,标记和要维护的数据等属性。

1
2
3
struct boki {
int l,r;ll sum,tag;
}b[350];

开始时,递推预处理出每个块的左右端点,对最后可能产生的不完整块进行特判。最后统计该块对应的区间和,并处理出区间中的每一个位置属于那一块。

1
2
3
4
5
6
7
8
void init() {
b[0].r=1;
for(int i=1;i<=k;++i) {b[i].l=b[i-1].r;b[i].r=b[i].l+len;}
if(b[k].r<=n) {b[k+1].l=b[k].r;b[k+1].r=n+1;++k;}
for(int i=1;i<=k;++i)
for(int j=b[i].l;j<b[i].r;++j)
b[pos[j]=i].sum+=seq[j];
}

分块维护区间和

进行区间修改时,对于一个完整块,只需用一个变量维护修改的值,而对于一个不完整块,直接进行暴力修改并更新其所在完整块的区间和;进行区间求和时,对于一个完整块,只需将其区间和加上块的长度乘修改累加的值。

1
2
3
4
5
6
7
8
9
10
11
void modify(int l,int r,ll d) {
int lp=pos[l],rp=pos[r-1];
if(lp==rp) { // 如果在同一块 暴力跑掉
for(int i=l;i<r;++i) seq[i]+=d;
b[lp].sum+=d*(r-l);
} else {
for(int i=lp+1;i<rp;++i) b[i].tag+=d;
for(int i=l;i<b[lp].r;++i) seq[i]+=d; b[lp].sum+=d*(b[lp].r-l);
for(int i=b[rp].l;i<r;++i) seq[i]+=d; b[rp].sum+=d*(r-b[rp].l);
}
}

区间查询可以仿照区间修改的思路。对完整块直接加上其区间长度乘标记和其区间和;对于非完整块,则直接暴力统计再加上非完整块长度乘标记。

1
2
3
4
5
6
7
8
9
10
11
12
inline ll query(int l,int r) {
ll ans=0;int lp=pos[l],rp=pos[r-1];
if(lp==rp) {
for(int i=l;i<r;++i) ans+=seq[i];
ans+=b[lp].tag*(r-l);
} else {
for(int i=lp+1;i<rp;++i) ans+=b[i].sum+b[i].tag*(b[i].r-b[i].l);
for(int i=l;i<b[lp].r;++i) ans+=seq[i]; ans+=b[lp].tag*(b[lp].r-l);
for(int i=b[rp].l;i<r;++i) ans+=seq[i]; ans+=b[rp].tag*(r-b[rp].l);
}
return ans;
}

虽然分块的时间复杂度为 O(N)O(\sqrt N),但是在常数小,数据不大时跑得比线段树还快。

分块维护区间最值

Goo!

分块维护区间积

Goo!

分块维护区间众数

Goo!

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

笔记 数据结构

评论

您需要成为穿墙的邪仙以加载 Disqus。