分块含义
分块是一种思想,而不是一种数据结构。
分块的基本思想是,通过对原数据的适当划分,并在划分后的每一个块上预处理部分信息,从而较一般的暴力算法取得更优的时间复杂度。
时间复杂度
分块的时间复杂度主要取决于分块的块长,一般可以通过均值不等式求出某个问题下的最优块长,以及相应的时间复杂度。
均衡不等式
对于我们初中所学的完全平方公式 (x+y)2≥0 经过简单的变形可以得到 x2+y2≥2xy
我们把 x=a , y=b 带入可以得到 a+b≥2ab (a,b>0) ,在 a=b 时取等号,这就是均衡不等式
分析
以一道题目为例:线段树1
没错,虽然是线段树的模板题,但也可以用分块来做,而且跑的贼快
我们设块长为 s ,无论什么[l, r]操作都是
- l,r 在同一块中,枚举: O(s)
- l,r 不在同一块中:枚举 l 所在块,枚举 l 所在块的下一个 到 r 所在块的上一个,枚举 r 所在块: O(s+sn)
共有 m 次操作的话,总时间复杂度就是 O(m(s+sn)) ,利用均衡不等式我们可知
当 s=sn 时该式子取得值最小,即时间复杂度最优,此时 s=n
(tips:对于不同的题目可能块长 s 不一样,要具体分析,但一般来说类似此题这种操作的块长取得都是 n)
模板
对于刚刚的那道线段树题目,我们可以写出分块的代码
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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
| #include <bits/stdc++.h>
using namespace std; const int N = 1e5 + 5;
int n, m; long long a[N], blk[N], b[N]; int pos[N]; int R;
void add(int l, int r, long long k) { if(pos[l] == pos[r]) { for(int i = l;i <= r;i++) a[i] += k; blk[pos[l]] += (r - l + 1) * k; return; } for(int i = l;pos[i] == pos[l];i++) { a[i] += k; blk[pos[i]] += k; } for(int i = pos[l] + 1;i <= pos[r] - 1;i++) { blk[i] += R * k; b[i] += k; } for(int i = r;pos[i] == pos[r];i--) { a[i] += k; blk[pos[i]] += k; } }
long long query(int l, int r) { long long ans = 0; if(pos[l] == pos[r]) { for(int i = l;i <= r;i++) { ans += a[i] + b[pos[i]]; } return ans; } for(int i = l;pos[i] == pos[l];i++) { ans += a[i] + b[pos[i]]; } for(int i = pos[l] + 1;i <= pos[r] - 1;i++) { ans += blk[i]; } for(int i = r;pos[i] == pos[r];i--) { ans += a[i] + b[pos[i]]; } return ans; }
int main() { clock_t c1 = clock(); #ifdef LOCAL freopen("in.in", "r", stdin); freopen("out.out", "w", stdout); #endif scanf("%d%d", &n, &m); R = sqrt(n) + 1;
for(int i = 1;i <= n;i++) { scanf("%lld", &a[i]); pos[i] = i / R + 1; blk[pos[i]] += a[i]; } long long opt, x, y, z; while(m--) { scanf("%lld", &opt); if(opt == 1) { scanf("%lld%lld%lld", &x, &y, &z); add(x, y, z); } else if(opt == 2) { scanf("%lld%lld", &x, &y); printf("%lld\n", query(x, y)); } }
end: cerr << "Time Used:" << clock() - c1 << "ms" << endl; return 0; }
|
tips:
- pos 数组记录的是每个元素所在的块的编号
- blk 数组记录的是每个块内实际的和
- b 数组像是线段树里的 lazytag 记录的是已经加到 blk 数组里的,但还没有“下传”到原数组里的值(但是这里不用下传也可以,代码里就没有下传)
其他题目
单点修改+查询区间内小于(等于)或大于(等于)某数的个数
对于每一个块,我们可以建立一个vector并排序。当修改的时候,二分查到vector内这个数所在的位置,erase掉,插入然后再排序
查询的话,不是完整块就暴力枚举,是完整块用vector的 lower_bound 查询个数就行了