这个人讲的特别好：

分块是一种暴力数据结构，可以处理区间操作等问题。

分块，就是分很多块来进行处理，这样查询时可以直接调用整块信息+暴力查询左右两端信息，将线性的枚举优化。

 

要分块，首先要确定块的大小。

一般来说，块的大小都为√n。这样可以保证整个序列被分成√n块，查询的时间复杂度可以达到平均。

分块算法中需要记录的信息有：

int sum[maxn]; //一个块的和int l[maxn]; //一个块的左端点（起点）int r[maxn]; //一个块的右端点（终点）int w[maxn]; //原数组int bel[maxn]; //第x个元素属于第bel[i]个块int siz; //块的大小，一般siz = sqrt(n)就可以了

初始分块

void build(int x){    for(int i = 1;i <= n;i++)        bel[i] = (i-1)/siz+1;    for(int i = 1;i <= bel[x];i++){        l[i] = (i-1)*siz+1;        r[i] = min(i*siz,x);        sum[i] = 0;    }}

区间修改

　　先修改左端的不完整块，如果右边还有不完整块就再修改右边，最后修改整块的

void add(int a,int b,int c){    for(int i = a;i <= min(bel[a]*siz,b);i++)        v[i] += c;    if(bel[a] != bel[b])        for(int i = (bel[b]-1)*siz+1;i <= b;i++)            v[i] += c;    for(int i = bel[a]+1;i <= bel[b]-1;i++)        lazy[i] += c;}

　　如果是区间乘法，需要每次暴力修改两端时先把lazy标记清除掉，

　　修改整块的lazy标记时，默认乘法优先，所以需要每次把加法的lazy标记也乘以要修改的数。

　　注意乘法的lazy标记要初始为1而不是0。

void reset(int x){    for(int i = l[x];i <= r[x];i++)        w[i] = (w[i]*mlaz[x] + alaz[x]) %mod;    alaz[x] = 0;    mlaz[x] = 1;}void multiply(int a,int b,int c){    reset(bel[a]);    for(int i = a;i <= min(r[bel[a]],b);i++)        w[i] *= c;    if(bel[a] != bel[b]){        reset(bel[b]);        for(int i = l[bel[b]];i <= b;i++)            w[i] *= c;    }    for(int i = bel[a]+1;i <= bel[b]-1;i++){        mlaz[i] *= c;        alaz[i] *= c;    }}

 区间查询

　　其实一般lazy*siz就行了，但是r-l+1可以处理最后的完整块不足siz之类的情况(不过究竟会不会出现呢...)

int query(int a,int b){    int ans = 0;    for(int i = a;i <= min(r[bel[a]],b);i++)        ans += w[i] + lazy[bel[a]];    if(bel[a] != bel[b])        for(int i = l[bel[b]];i <= b;i++)            ans += w[i] + lazy[bel[b]];    for(int i = bel[a]+1;i <= bel[b]-1;i++)        ans += sum[i] + (r[bel[i]]-l[bel[i]]+1)*lazy[i];    return ans;

拓展

为什么要用分块？因为树状数组和线段树不好写

当树状数组和线段树不能直接套板子，需要比较大的改动，而分块看起来比较好膜改而且大概可以解决时

比如——

1.给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。

借用hzwer说的 数列简单分块问题实际上有三项东西要我们思考：对于每次区间操作：

• 不完整的块的O(√n)个元素怎么处理？
• O(√n)个 整块怎么处理？
• 要预处理什么信息（复杂度不能超过后面的操作）？

对于这道题，要求每个块内的数据是有序的，可以考虑用一个vector来维护

修改函数、lazy标记的用法不变，

在初始分块和修改两端时需要重置，即把这个块内的数据重新排序。

vector
      
        ve[maxn];void reset(int x) {    ve[x].clear();    for (int i = l[x]; i <= r[x]; i++) ve[x].push_back(w[i]);    sort(ve[x].begin(), ve[x].end());}int query(int a, int b, int c) {    int ans = -1;    for (int i = a; i <= min(r[bel[a]], b); i++) {        int now = lazy[bel[a]] + w[i];        if (now < c)            ans = max(ans, now);    }    if (bel[a] != bel[b])        for (int i = l[bel[b]]; i <= b; i++) {            int now = lazy[bel[b]] + w[i];            if (now < c)                ans = max(ans, now);        }    for (int i = bel[a] + 1; i <= bel[b] - 1; i++) {        int d = c - lazy[i];        vector
       
        ::iterator it = lower_bound(ve[i].begin(), ve[i].end(), d) - 1;        if (*it < d && it >= ve[i].begin() && it <= ve[i].end())            ans = max(ans, *it + lazy[i]);    }    return ans;}
       
      

 

2. 给出一个长为 n 的数列，以及 n 个操作，操作涉及单点询问（第x个数），单点插入（第x个数前）。

每次将一个元素插入到某个元素的前面。有了前一道题的经验，很容易想到用vector存块。

但是这样要膜改的东西就比较多了，因为每个vector的长度都是不同的。

查询时，无法直接确定它在哪一个块内，需要每次调用当前块的size。

插入时，首先查询插入的前一个元素在哪一个块内，再把这个元素插入到对应的块里。

但是当某一个块过大时，需要的暴力操作就会过多，导致时间复杂度爆炸。

为了避免这种情况，需要引入一个操作：重新分块（重构）

每√n次插入后，重新把数列平均分一下块，重构需要的复杂度为O(n)，重构的次数为√n，复杂度没有问题，而且保证了每个块的大小相对均衡。

当然，也可以当某个块过大时重构，或者只把这个块分成两半。

struct node {    int bel, num;};node query(int x) {    node ans;    int now = 1;    while (x > ve[now].size()) x -= ve[now++].size();    ans.bel = now;    ans.num = x - 1;    return ans;}void rebuild() {    int cnt = 0;    int q[maxn];    for (int i = 1; i <= tot; i++) {        for (int j = 0; j < ve[i].size(); j++) q[++cnt] = ve[i][j];        ve[i].clear();    }    int new_siz = sqrt(cnt);    for (int i = 1; i <= cnt; i++) ve[(i - 1) / new_siz + 1].push_back(q[i]);    tot = (cnt - 1) / new_siz + 1;}void insert(int a, int b) {    node last = query(a);    ve[last.bel].insert(ve[last.bel].begin() + last.num, b);    if (ve[last.bel].size() > 2 * siz)        rebuild();}

 

3.给出一个长为 n的数列​，以及 n 个操作，操作涉及区间开方，区间求和。

 ん？（察觉）

开方不能对区间直接操作，但是暴力算法的时间复杂度显然不够。

通过查看题解思考可以发现，由于操作只有下开方，几次操作后，一个块内的数字会全部变为0或1，这一块的操作就可以跳过了。

开一个bool数组记录这一块是否还有不是0或1的数字，否则暴力。其他函数不变。

void radic(int a,int b){    if(a > b)swap(a,b);    for(int i = a;i <= min(r[bel[a]],b);i++){        if(flag[bel[a]])break;        sum[bel[a]] -= w[i];        w[i] = sqrt(w[i]);        sum[bel[a]] += w[i];    }    if(bel[a] != bel[b])        for(int i = l[bel[b]];i <= b;i++){            if(flag[bel[b]])break;            sum[bel[b]] -= w[i];            w[i] = sqrt(w[i]);            sum[bel[b]] += w[i];        }    for(int i = bel[a]+1;i <= bel[b]-1;i++){        if(flag[i])continue;        flag[i] = true;        sum[i] = 0;        for(int j = l[i];j <= r[i];j++){            w[j] = sqrt(w[j]);            sum[i] += w[j];            if(w[j] > 1)flag[i] = false;        }    }}

 

 

最后一个我还不会写，QAQ