块状数组
一、块状数组的引入
这一节课中，我们还是来解决区间类的问题，不过这一次，我们会把整个序列划分为若干个小块，对整块整体操作，对零散的块单独处理。这就是分块的思想。
假设序列的长度为 n，操作的数量为q。块状数组就是把原序列划分成了B块，每块的大小为⌊n/B⌋，在询问的时候，对于整块的区间整体处理，对于零散的块单独处理，时间复杂度为，O(B+⌊n/B⌋)，其中 B取 sqrt(n) 时候复杂度最优。
分块实质上就是三层的树，每个非叶子结点的节点有sqrt(n)个子节点。
我们为了能够整体处理完整的区间，所以在需要根据题目的要求，在第二层的块上，维护一些信息，最常见的有处理区间加法的lazy标记等等。
我们来看一个例子，我们如果想要对某一段区间进行在线操作（一边修改一边查询），每
次操作对某个区间l，r加上c，然后再进行查询区间[1，r]的和，我们可以怎么做呢?
二、块状数组的代码实现
1. 确定每一个块的大小，以及块的左端点和右端点，同时明确每一个点属于哪一个区间。
int L[N], R[N], belong[N];
//L[i] 表示第i个点的左端点
//R[i] 表示第i个点的右端点
//belong[i] 表示i点属于belong[i]这个快
void init(){
len = sqrt(n); //每个块的长度
num = (n - 1) / len + 1; //一共有num个块
//对于每一个快，确定左右边界
for(int i = 1; i <= num; i++){
L[i] = R[i - 1] + 1;
R[i] = i * len;
}
R[num] = n;
//对于每一个i，明确她属于哪一个块
for(int i = 1; i <= n; i++){
belong[i] = (i - 1) / len + 1;
}
}2.把每个数读取进来，并且求出块内元素和。
long long sum[N], lazy[N];
//sum[i] 表示第i个块的块内元素和
//lazy[i] 表示第i个块的块标记
cin >> n;
init();
for(int i = 1; i <= n; i++){
cin >> a[i];
//统计块内元素和
sum[belong[i]] += a[i];
}3.对于修改操作，我们首先需要确定的是需要修改的区间[l，r]的左右端点，分别是在哪个块中。
其次按照我们之前所说的原则，零散的块单独处理修改原数组的值，更新块内元素和。完整的块整体处理，更新块标记和块内元素和。
void update(int l, int r, int c){
//l属于bl这个块，r属于br这个块
int bl = belong[l], br = belong[r];
//在同一个块中，直接暴力处理
for(int bl == br){
//修改元素
for(int i = 1; i <= r; i++){
a[i] += c;
}
//更新块内元素和
sum[bl] += (r - l + 1) c;
return;
}
//[l, r[bl] 零散的块，修改元素，更新块内元素和
//[bl + 1, br - 1] 完整的块 更新块标记，更新块内元素和
//[l[br], r] 零散的块，修改元素，更新块内元素和
for(int i = 1; i <= R[bl]; i++){
a[i] += c;
}
sum[bl] += (R[bl] - l + 1) c;
for(int i = bl + 1; i <= br - 1; i++){
lazy[i] += c;
sum[i] += len c;
}
for(int i = L[br]; i <= r; i++){
a[i] += c;
}
sum[br] += (r - l[br] + 1) c;
}5.对于查询操作，我们同样需要先确定的是需要修改的区间[l,r]的左右端点，分别是在哪个块中。之后对于零散的块单独处理，除了要加上原数组的值，还要加上块标记。完整的块整体处理，只需要加上块内元素和即可。
long long query(int l, int r){
//l属于bl这个块，r属于br这个块
int bl = belong[l], br = belong[r];
//在同一个块中，直接暴力处理
long long res = 0;
if(bl == br){
for(int i = 1; i <= r; i++){
res += a[i];
}
res += (r - l + 1) lazy[bl];
return res;
}
////[l, r[bl] 零散的块，暴力累加，再加上块标记
//[bl + 1, br - 1] 完整的块 返回块内元素和
//[l[br], r] 零散的块，暴力累加，再加上块标记
for(int i = 1; i <= R[bl]; i++){
res += a[i];
}
res += (R[bl] - l + 1) lazy[bl];
for(int i = bl + 1; i <= r; i++){
res += sum[i];
}
for(int i = L[br]; i <= r; i++){
res += a[i];
}
res += (r - L[br] + 1) * lazy[br];
return res;
}三、例题讲解-【模板】块状数组区间修改、区间查询
题目描述
这是一道模板题。
给定数列 a[1]，a[2]，...，a[n]，你需要依次进行 Q 个操作，操作有两类：
1 l r x：给定 l，r，x，对于所有 i ∈ [l, r]，将 a[i] 加上 x。
2 l r：给定 l，r，求 ∑(i=l to r)a[i] 的值。
输入格式
第一行包含 2 个正整数 n，Q，表示数列长度和询问个数。保证 1 ≤ n, Q ≤ 10^6。
第二行 n 个整数 a[1]，a[2]，...，a[n]，表示初始数列。保证 |a[i]| ≤ 10^6。
接下来 Q 行，每行一个操作，为以下两种之一：
1 l r x：对于所有 i ∈ [l, r]，将 a[i] 加上 x。
2 l r：输出 ∑(i=l to r)a[i] 的值。
保证 1 ≤ l ≤ r ≤ n，|x| ≤ 10^6。
输出格式
对于每个 2 l r 操作，输出一行，每行有一个整数，表示所求的结果。
提示
1≤n, q≤5e4
|x|≤10000
|A[i]|≤1e9
题目分析
模板题，按照讲解的块状数组代码实现做即可：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10;
LL a[N];
int L[N], R[N], belong[N];
// L[i] 表示第 i 个点的左端点
// R[i] 表示第 i 个点的右端点
// belong[i] 表示 i 点属于 belong[i] 这个块
LL sum[N], lazy[N];
// sum[i] 表示第 i 个块的块内元素和
// lazy[i] 表示第 i 个块的块标记
int n, m, num, len;
void init() {
len = sqrt(n); // 每个块的长度
num = (n - 1) / len + 1; // 一共有 num 个块
// 对于每一个块，确定左右边界
for (int i = 1; i <= num; i++) {
L[i] = R[i - 1] + 1;
R[i] = i len;
}
R[num] = n;
// 对于每一个 i，明确它属于哪一个块
for (int i = 1; i <= n; i++) {
belong[i] = (i - 1) / len + 1;
}
}
void update(int l, int r, int c) {
// l 属于 bl 这个块，r 属于 br 这个块
int bl = belong[l], br = belong[r];
// 在同一个块中，直接暴力处理
if (bl == br) {
// 修改元素
for (int i = l; i <= r; i++) {
a[i] += c;
}
// 更新块内元素和
sum[bl] += (r - l + 1) c;
return;
}
// [l, R[bl]] 零散的块，修改元素，更新块内元素和
// [bl + 1, br - 1] 完整的块，更新块标记，更新块内元素和
// [L[br], r] 零散的块，修改元素，更新块内元素和
for (int i = l; i <= R[bl]; i++) {
a[i] += c;
}
sum[bl] += (R[bl] - l + 1) c;
for (int i = bl + 1; i <= br - 1; i++) {
lazy[i] += c;
sum[i] += len c;
}
for (int i = L[br]; i <= r; i++) {
a[i] += c;
}
sum[br] += (r - L[br] + 1) c;
}
long long query(int l, int r) {
// l 属于 bl 这个块，r 属于 br 这个块
int bl = belong[l], br = belong[r];
// 在同一个块中，直接暴力处理
long long res = 0;
if (bl == br) {
for (int i = l; i <= r; i++) {
res += a[i];
}
res += (r - l + 1) lazy[bl];
return res;
}
// [l, R[bl]] 零散的块，暴力累加，再加上块标记
// [bl + 1, br - 1] 完整的块，返回块内元素和
// [L[br], r] 零散的块，暴力累加，再加上块标记
for (int i = l; i <= R[bl]; i++) {
res += a[i];
}
res += (R[bl] - l + 1) lazy[bl];
for (int i = bl + 1; i <= br - 1; i++) {
res += sum[i];
}
for (int i = L[br]; i <= r; i++) {
res += a[i];
}
res += (r - L[br] + 1) lazy[br];
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
init();
for (int i = 1; i <= n; i++) {
cin >> a[i];
// 统计块内元素和
sum[belong[i]] += a[i];
}
while (m--) {
int op, x, y, z;
cin >> op;
if (op == 2) {
cin >> x >> y;
cout << query(x, y) << "\n";
} else {
cin >> x >> y >> z;
update(x, y, z);
}
}
return 0;
}