数列分块
其实，分块是一种思想，而不是一种数据结构。——OI-wiki
分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。
分块的时间复杂度主要取决于分块的块长，快长一般取 \(\sqrt{n}\) 时，时间复杂度时最优的。
P13976 数列分块入门 1
很板很板的分块板子
用Tag来维护每个块的区间加操作
注意开longlong
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int QWQ = 3e5 + 5;
int n, m, a[QWQ], tag[QWQ], block, col[QWQ], num;
struct node
{int l, r;
}b[QWQ];
void update(int l, int r, int c)
{if(col[l] == col[r]){for(int i = l;i <= r;i ++){a[i] += c;}return ;}for(int i = l; i <= b[col[l]].r; i++){a[i] += c;}for(int i = b[col[r]].l; i <= r; i++){a[i] += c;}for(int i = col[l] + 1; i < col[r]; i++){tag[i] += c;}
}
signed main()
{cin >> n;block = sqrt(n);num = n / block;if(n % block != 0)num ++;for(int i = 1;i <= n;i ++){cin >> a[i];col[i] = (i - 1) / block + 1;} for(int i = 1;i <= num;i ++){b[i].l = block * (i - 1) + 1;b[i].r = min(block * i, n);}b[num].r = n;while(n --){int op, l, r, c;cin >> op >> l >> r >> c;if(op == 0){update(l, r, c);}if(op == 1){cout << a[r] + tag[col[r]] << endl;}}
}