分块的基本思想是通过适当的划分，预处理一部分信息并保存下来，用空间换取时间，达到时空平衡。

分块与树状数组和线段树相比，更加通用、容易实现，可以维护一些复杂的信息。大部分常见的分块思想都可以用“大段维护、局部朴素”来形容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 分块
// 分块相关数据结构
int R[SIZE], L[SIZE], pos[SIZE];  // 每段的左右端点、每个妹纸属于哪一段
int t, len;
int sum[SIZE];  // 每块的和
int add[SIZE];  // 每块的增量标记


int init() {
    t = sqrt(n);   // 块数
    len = t==0? n: n/t;  // 每块的长度
    for (int i = 1; i <= t; ++i) {
        L[i] = (i-1)*len + 1;
        R[i] = i*len;
    }
    if (R[t] < n) {
        L[t+1] = R[t]+1;
        R[++t] = n;
    }
}

待补充