最近cf刷的有点难，请教一位大神，大神曰，“汝之惑，分块也”，所以小菜鸡来学分块了。

数列分块

分块是我感觉是最优雅的暴力了，适用于同时区间修改和区间查询，而且书写十分方便。对于动态维护序列的题目我们一般会想到树状数组和线段树结构。

树状数组的限制十分明显，不能同时进行区间修改和区间查询地操作，只能支持单点修改+区间查询或者是区间修改和单点查询。虽然此题可以用树状数组做，但是主要还是练习一下分块。

线段树可以说是非常棒的动态维护序列的数据结构了，时间复杂度非常优秀，但是书写起来十分复杂。

分块也并不是万能的，如果同时区间修改和区间查询且数据范围在1e6的范围，那么分块就很可能超时了，此时只能使用线段树结构去维护这个序列。

各有优缺点吧，主要是分块的这个思想得学会，在很多地方都用得到。

下面给出分块算法中的一些特有名词

区间：数列中连续一段的元素

区间操作：将某个区间[a,b]的所有元素进行某种改动的操作

块：我们将数列划分成若干个不相交的区间，每个区间称为一个块

整块：在一个区间操作时，完整包含于区间的块

不完整的块：在一个区间操作时，只有部分包含于区间的块，即区间左右端点所在的两个块

入门1

本道练习题在loj上，链接已经给出。

数据范围在5w，如果用朴素的算法那么必超时的。这个时候我们可以把整个序列分成一块一块的，那么到底怎么分呢，最优的分法应该是每一块包含(int)sqrt(n)个数据，最多能把数据分成(int)sqrt(n)+1块。那么在进行一次区间修改的时候，我们同样可以把区间按照分块的方式去操作，对于一个区间分出的每一个块，如果这个块有sqrt(n)个数据那么称这个块是完整的，否则是不完整的。对于完整的块，我们可以给一个标记数组，标记这个块整体都被加上了某个值；对于不完整的块我们可以对整个不完整的块内的数据进行单点修改。那么一次区间修改的操作复杂度就是sqrt(n)了。单点查询的时候只需要找到那个元素的值加上那个元素所在区间的标记就是该元素的实际值。

这里需要考虑以下几种情况：

左端点在块的起点，右端点不在另一个块的终点：需要先处理右端点所在的不完整的块的元素值之后，对剩下的完整的块进行区间标记。

左端点不在块的起点，右端点在另一个块的终点：需要先处理左端点所在的不完整的块的元素值之后，对剩下的完整的块进行区间标记。

左端点在块的起点，右端点在另一个块的终点：直接对所有块进行标记即可。

左端点与右端点在同一个块上，且完整占据整个块：直接对该块标记。

左端点与右端点在同一个块上，且不完整占据整个块：直接对区间内的元素进行修改即可。

刚开始考虑情况不周，导致WA了很多次，下面贴出AC代码和测评情况。

标程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define maxn 50005
using namespace  std;
int a[maxn];
int block[1001];

int main(){
    //freopen("1.txt","r",stdin);
    int n;
    cin>>n;
    int q=n;
    int block_size=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    while(q--){
        int opt,l,r,c,i;
        cin>>opt>>l>>r>>c;
        if(opt==0){
            if((l-1)/block_size==(r-1)/block_size){
                if((l-1)%block_size==0&&r%block_size==0){
                    block[(l-1)/block_size+1]+=c;
                }
                else{
                    for(int i=l;i<=r;i++){
                        a[i]+=c;
                    }
                }
                continue;
            }
            
            if((l-1)%block_size!=0){
                for(i=l;i<=min(((l-1)/block_size+1)*block_size,r);i++){
                    a[i]+=c;
                }
                l=i-1;
            }
            
            if(r%block_size!=0){
                
                for(i=max((r-1)/block_size*block_size+1,l);i<=r;i++){
                    a[i]+=c;
                }
                r=r/block_size*block_size;
            }
            for(i=l/block_size+1;i<=r/block_size;i++){
                block[i]+=c;
            }
        }
        else{
            printf("%d\n",a[r]+block[(r-1)/block_size+1]);
        }
    }
    return 0;
}

本蒟蒻测评的状况

这算正式入门了以下这个分块吧，后面把这个分块的所有入门都做了先。