分块
分块即为将整个序列分为多个块来处理区间信息，常的操作需支持修改和查询。
一个区间，它一定由一些完整的块和剩余的单点。对于完整的块，我们直接对整个块一起做修改和查询；对于剩余的单点，我们直接暴力修改。
通常块长被分为 \(\sqrt{n}\) ，时间复杂度为 \(O(n\sqrt{n})\)
代码模板：
int n, a[N]; //原数组
int p, pos[N]; //块长 和 每个点属于的块编号
int m, l[N], r[N]; //块的数量 和 每个块的左右端点
int b[N], k[N]; //查询用数组 和 记录块修改的数组
inline void work(){ //预处理
p = sqrt(n);
m = ceil(1.0 * n / p); //计算块数
for(int i = 1; i <= m; ++ i){
l[i] = r[i - 1] + 1;
r[i] = i * p; //计算块左右端点
for(int j = l[i]; j <= r[i]; ++ j){
pos[j] = i; //记录当前点块编号
b[i] = a[i]; //看题目要求
}
}
}
inline void add(int x, int y){ //修改区间[x, y]
for(int i = x; i <= min(y, r[pos[x]]); ++ i){ //左剩余区间
a[i] + ? //看题目要求
}
if(pos[x] != pos[y]){ //左右剩余不重
for(int i = max(l[pos[y]], x); i <= y; ++ i){ //右剩余区间
a[i] + ? //同上
}
}
for(int i = pos[x] + 1; i <= pos[y] - 1; ++ i){ //整块修改
k[i] + ?//同上
}
}
inline int ask(int x, int y){ //查询区间
int sum = 0;
for(int i = x; i <= min(y, r[pos[x]]); ++ i){ //左剩余区间
sum += a[i]? //看题目要求
}
if(pos[x] != pos[y]){ //左右剩余不重
for(int i = max(l[pos[y]], x); i <= y; ++ i){ //右剩余区间
sum += a[i]? //同上
}
}
for(int i = pos[x] + 1; i <= pos[y] - 1; ++ i){ //整块修改
sum += k[i]? //同上
}
return sum;
}