其实我认为分块并不完全算是一种数据结构，它应该是一种分段思想，但为了正式一点，还是写了这一篇文章。

首先放一道最基本的分块：

P3870 [TJOI2009] 开关 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//code by SPzos
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#define ak return 0;
#define fo(i,j,k) for(register int i=j;i<=k;++i)
#define fd(i,j,k) for(register int i=j;i>=k;--i)
#define fh(i,x) for(register int i=head[x];i;i=e[i].nxt)
#define fv(i,x) for(register int i=0;i<v[x].size();++i)
using namespace std;
const int N=100010;
inline int read(){
    int ret=0,f=0;char ch=getchar(); 
    while(ch<'0' || ch>'9'){if(ch=='-') f=1;ch=getchar();}
    while(ch>='0' && ch<='9'){ret=(ret<<1)+(ret<<3)+ch-(1<<4)-(1<<5);ch=getchar();}
    return f?-ret:ret;
} 
int n,m,a[N],b[N],tag[N],ans[N],sq;
inline void change(int x,int y){
    fo(i,x,min(b[x]*sq,y)){
        ans[b[x]]-=(a[i]^tag[b[x]]);
        a[i]^=1;
        ans[b[x]]+=(a[i]^tag[b[x]]);
    }
    if(b[x]!=b[y])
    fo(i,(b[y]-1)*sq+1,y){
        ans[b[y]]-=(a[i]^tag[b[y]]);
        a[i]^=1;
        ans[b[y]]+=(a[i]^tag[b[y]]);
    }
    fo(i,b[x]+1,b[y]-1){
        tag[i]^=1;
        ans[i]=sq-ans[i];
    }
}
inline int query(int x,int y){
    int sum=0;
    fo(i,x,min(b[x]*sq,y)){
        sum+=(a[i]^tag[b[x]]);
    }
    fo(i,b[x]+1,b[y]-1) sum+=ans[i];
    if(b[x]!=b[y]) 
    fo(i,(b[y]-1)*sq+1,y){
        sum+=(a[i]^tag[b[y]]);
    }
    return sum;
}
int main(){
    n=read();m=read();
    sq=sqrt(n);
    fo(i,1,n) b[i]=(i-1)/sq+1;
    fo(i,1,m){
        int opt=read(),x=read(),y=read();
        if(opt) printf("%d\n",query(x,y));
        else change(x,y);
    }
    ak
} 

其实分块这个东西就是个优雅的暴力，把数列分成一块块的，如果能整体修改那就上懒标记，如果不能就直接暴力修改

这里提一个扩展，不算是分块，但是属于根号算法。

根号算法--不只是分块

P3396 哈希冲突 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//code by SPzos
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#define fo(i,j,k) for(register int i=j;i<=k;++i)
#define fd(i,j,k) for(register int i=j;i>=k;--i)
#define fh(i,x) for(register int i=head[x];i;i=e[i].nxt)
#define fv(i,x) for(register int i=0;i<v[x].size();++i)
using namespace std;
const int N=150010;
inline int read(){
    int ret=0,f=0;char ch=getchar(); 
    while(ch<'0' || ch>'9'){if(ch=='-') f=1;ch=getchar();}
    while(ch>='0' && ch<='9'){ret=(ret<<1)+(ret<<3)+ch-(1<<4)-(1<<5);ch=getchar();}
    return f?-ret:ret;
} 
int n,m,val[N],ans[505][505];
int main(){
    n=read();m=read();
    int sq=sqrt(n);
    fo(i,1,n){
        val[i]=read();
        fo(j,1,sq){
        ans[j][i%j]+=val[i];
        }
    }
    while(m--){
        char ch[2];scanf("%s",ch);
        int x=read(),y=read();
        if(ch[0]=='A'){
            int as=0;
            if(x<=sq) as=ans[x][y];
            else{
                for(int i=y;i<=n;i+=x)
                    as+=val[i];
                }
                printf("%d\n",as);
        }
           else{
                fo(p,1,sq){
                    ans[p][x%p]-=val[x];
                    ans[p][x%p]+=y;
                }
                val[x]=y;
            }
        }
    return 0;
} 

预处理的复杂度为nlogn

问题询问为mlogn，因为模数比根号n更大，这就保证了数比根号N要小

总计(m+n)logn

这种算法确实是很妙，我目前也只是碰见了这一道。