前言
某人:线段树好难，学不会，树状数组感觉用途少好多，怎么办啊
Ben:入我分块神教！
ps:作者不认为分块是数据结构，而是一种思想。本文代码来自作者不同时期，马蜂习惯存在差别
前置芝士:循环，数组，没了
一 序列分块
对于给定序列要求增删改查类问题，一般最常用线段树和BIT，毕竟是高贵的log
但是假如对复杂度没有那么高要求，存不存在一种更好理解、更不容易写错的东西来代替呢?
现在介绍--分块
我们可以把一个数列划分成若干个等长的块
设块长为 \(B\)，则我们可以整体化处理一些信息
以区间加法、求和为例(假设 \(B=2\) )
考虑对于数列\(a={1,1,4,5,1,4,1}\)
可以划分为\(a={1,1|4,5|1,4|1}\)
最后落单了个1怎么办？不影响不用管它
修改大概可以分为三个部分:
中间整块、两边不完整部分
考虑整块处理，预处理时处理好每个下标所在的块(块的左右端点可记可不记)和块内初始和。发现我们可以参考线段树，我们在块上打个标记记录增加量
整块最多有\(\frac{n}{B}\)量级个，复杂度\(O(\frac{n}{B})\)
散块呢?我们可以暴力处理(毕竟只有两个),\(O(B)\)
查询同理，对于每个整块将答案加上(初始和+长度\(\times\)标记)，散块暴力累加(记得加上标记)
那么 \(B\)应该取多少呢?
我们肯定希望两种操作操作和尽可能小
由均值不等式，\(B+\frac{n}{B}>=2\sqrt n\)，当左边两项相等时，即\(B=\sqrt n\)时最小。对于两个操作复杂度可以用\(B\)表示时，当两式相等\(B\)最佳，不一定是\(\sqrt n\)(不过你一般写\(\sqrt n\)人家也不会卡除了ynoi)
例题:线段树1
讲解见上，代码参考:
#include<bits/stdc++.h>
using namespace std;
inline long long read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
long long k[1114514],a[1114514],mx[1114514],mark[114514];
long long n,m;
int main(){
n=read();m=read();
int bl=sqrt(n);
for(int i=1;i<=n;i++){
cin>>a[i];
k[i]=(i-1)/bl+1;
mx[k[i]]+=a[i];
}
int la=k[n];
long long l,r,z,kk;
while(m--){
z=read();l=read(),r=read();
long long ans;
ans=0;
if(z==1){
kk=read();
if(k[l]==k[r] or k[l]+1==k[r]){
for(int i=l;i<=r;i++){
a[i]+=kk,mx[k[i]]+=kk;
}
}
else{
int ll=k[l],rr=k[r];
for(int i=l;k[i]==ll;i++){
a[i]+=kk,mx[k[i]]+=kk;
}
for(int i=r;k[i]==rr;i--){
a[i]+=kk,mx[k[i]]+=kk;
}
for(int i=ll+1;i<rr;i++){
mark[i]+=kk;
}
}
}
else{
if(k[l]==k[r] or k[l]+1==k[r]){
for(int i=l;i<=r;i++){
ans+=a[i]+mark[k[i]];
}
}
else{
int ll=k[l],rr=k[r];
for(int i=l;k[i]==ll;i++){
ans+=a[i]+mark[k[i]];
}
for(int i=r;k[i]==rr;i--){
ans+=a[i]+mark[k[i]];
}
for(int i=ll+1;i<rr;i++){
ans+=mx[i]+bl*mark[i];
}
}
cout<<ans<<"\n";
}
}
return 0;
}
例二:开关
即区间取反，同样打标记，设块内开\(W\)个灯，整块取反时区间开灯数变成 \(len-W\),散块直接暴力取反记录
code:
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}
const int N = 1e5 + 10;
int n, m;
int block, b[N];
int a[N], sum[N], tag[N];
void init(){
for (int i = 1; i <= n; i++){
b[i] = (i - 1) / block + 1;
}
}
void modify(int l,int r){
for(int i=l;i<=min(b[l]*block,r);i++) a[i]^=1,sum[b[i]]+=(a[i]^tag[b[i]]?1:-1);
if(b[l]!=b[r])
for(int i=(b[r]-1)*block+1;i<=r;i++)
a[i]^=1,sum[b[i]]+=(a[i]^tag[b[i]]?1:-1);
for(int i=b[l]+1;i<=b[r]-1;i++){
tag[i]^=1;
sum[i]=block-sum[i];
}
}
int query(int l, int r){
int ans = 0;
for(int i=l;i<=min(b[l]*block,r);i++) ans+=(a[i]^tag[b[l]]);
if(b[l]!=b[r])
for(int i=(b[r]-1)*block+1;i<=r;i++)
ans+=(a[i]^tag[b[r]]);
for(int i=b[l]+1;i<=b[r]-1;i++) ans+=sum[i];
return ans;
}
int main(){
n = read(), m = read();
block = sqrt(n);
init();
for (int i = 1; i <= m; i++){
int opt = read(), l = read(), r = read();
if (opt == 0){
modify(l, r);
}else{
printf("%d\n", query(l, r));
}
}
return 0;
}
其他例题:LOJ数列分块1~9，题解参考hzwer大佬官方,但注意三中官方题解代码存在锅，用set如果块内存在多个元素会误杀，建议和二一样写
前面太简单了对吧，来上强度(选看)
由乃打扑克（ynoi）
求一个数据结构，可以区间加和区间kth
看完上面数列分块第三题再来这里
考虑查询(操作姑且放一边)
考虑二分一个值，显然这个数的排名满足单调性，可二分
how to check?显然可以用分块
操作直接暴力操作后重构即可
好水啊！这也叫上强度？顶多有点难写
啊确实，这么写完你应该TLE
优化1:二分不需要从\(INTMAXMIN\)开始，从区间最大值最小值开始即可
优化2:一个整块若最大值都小于mid可以直接把排名+块长，最小值都大于可以
跳过
优化3:玄学块长，我是200左右比较优
加这三就可以过
优化四：对于两边散块修改后可以和原块归并做到严格的修改
其余优化见tj
code:(优化123)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
//#define int long long
inline int qread() {
register char c = getchar();
register int x = 0, f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + c - 48;
c = getchar();
}
return x * f;
}
int n,m,k[1005],bk,cg=1;
ll a[N],ad[10005],sum[10005],mx[10005],mi[10005];
vector<ll> B[20005];
int bl(int x){return (x-1)/bk+1;}
void remake(int k){
while(!B[k].empty())B[k].pop_back();
mx[k]=INT_MIN;
mi[k]=INT_MAX;
for(int i=(k-1)*bk+1;i<=min(n,k*(bk));i++) a[i]+=ad[k],B[k].push_back(a[i]),mx[k]=max(mx[k],a[i]),mi[k]=min(a[i],mi[k]);
sort(B[k].begin(),B[k].end());ad[k]=0;
}
void add(int l,int r,ll k){
for(int i=l;i<=min(bl(l)*bk,r);i++){a[i]+=k,sum[bl(i)]+=k;}
remake(bl(l));
if(bl(l)!=bl(r)){
for(int i=r;i>bk*(bl(r)-1);i--)
a[i]+=k,sum[bl(i)]+=k;
remake(bl(r));
}
for(int i=bl(l)+1;i<bl(r);i++) ad[i]+=k;
}
ll query(int l,int r,ll c){
ll ans=0;
for(int i=l;i<=min(bl(l)*bk,r);i++){ans+=(a[i]+ad[bl(i)]<c);}
if(bl(l)!=bl(r)){
for(int i=r;i>bk*(bl(r)-1);i--)
ans+=(a[i]+ad[bl(i)]<c);
}
for(int i=bl(l)+1;i<bl(r);i++){
int x=c-ad[i];
if(mx[i]<x){ans+=bk;continue;}
if(mi[i]>x){continue;}
ans+=lower_bound(B[i].begin(),B[i].end(),x)-B[i].begin();
}
return ans;
}
ll ask(int l,int r,ll k){
if(r-l+1<k or k<1) return -1;
ll L=-2e4*cg-5000,R=-L;
ll ans=-1;
while(L<=R){
ll mid=(L+R)>>1;
int yzy=query(l,r,mid);
if(yzy<k){
L=mid+1;
}
else R=mid-1,ans=mid;
}
return ans-1;
}
signed main(){
// freopen("data.in","r",stdin);
// freopen("ans.txt","w",stdout);
n=qread(),m=qread();
bk=65;
for(int i=1;i<=n;i++) a[i]=qread();
for(int i=1;i<=bl(n);i++) remake(i);
cg=1;
while(m--){
int f,l,r;ll k;
f=qread(),l=qread(),r=qread(),k=qread();
if(f==2) add(l,r,k),cg++;
else printf("%lld\n",ask(l,r,k));
}
}
非常好题目，恨来自中国
二 值域分块
某人:值域分块不是纯纯大废物，跑不过权值线段树/树状数组
当然，这样想是错误的
不妨我们来考虑一下权值分块的优点
显然可以想到的是，单点修改 \(O(1)\) 非常优秀
所以有一些修改特别多查询少的题目有奇效
但是这种情况未免太少了，还是废物