浅谈分块 - Histcat's Blog

916 字

5 分钟

浅谈分块

2022-08-09

oi

分块含义#

分块是一种思想，而不是一种数据结构。分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。

时间复杂度#

分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。

均衡不等式#

对于我们初中所学的完全平方公式 $(x+y)^2 \ge 0$ 经过简单的变形可以得到 $x^2+y^2 \ge 2xy$

我们把 $x = \sqrt{a}$ ， $y = \sqrt{b}$ 带入可以得到 $a + b \ge 2\sqrt{ab}$ $(a, b > 0)$ ，在 $a = b$ 时取等号，这就是均衡不等式

分析#

以一道题目为例：线段树1

~~没错，虽然是线段树的模板题，但也可以用分块来做，而且跑的贼快~~

我们设块长为 $s$ ，无论什么[l, r]操作都是

$l, r$ 在同一块中，枚举： $O(s)$
$l, r$ 不在同一块中：枚举 $l$ 所在块，枚举 $l$ 所在块的下一个到 $r$ 所在块的上一个，枚举 $r$ 所在块： $O(s + \frac{n}{s})$

共有 $m$ 次操作的话，总时间复杂度就是 $O(m(s + \frac{n}{s}))$ ，利用均衡不等式我们可知当 $s = \frac{n}{s}$ 时该式子取得值最小，即时间复杂度最优，此时 $s = \sqrt{n}$

（tips：对于不同的题目可能块长 $s$ 不一样，要具体分析，但一般来说类似此题这种操作的块长取得都是 $\sqrt{n}$ ）

模板#

对于刚刚的那道线段树题目，我们可以写出分块的代码

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
const int N = 1e5 + 5;
5

6
int n, m;
7
long long a[N], blk[N], b[N];
8
int pos[N];
9
int R;
10

11
void add(int l, int r, long long k)
12
{
13
    if(pos[l] == pos[r])
14
    {
15
        for(int i = l;i <= r;i++)
16
            a[i] += k;
17
        blk[pos[l]] += (r - l + 1) * k;
18
        return;
19
    }
20
    for(int i = l;pos[i] == pos[l];i++)
21
    {
22
        a[i] += k;
23
        blk[pos[i]] += k;
24
    }
25
    for(int i = pos[l] + 1;i <= pos[r] - 1;i++)
26
    {
27
        blk[i] += R * k;
28
        b[i] += k;
29
    }
30
    for(int i = r;pos[i] == pos[r];i--)
31
    {
32
        a[i] += k;
33
        blk[pos[i]] += k;
34
    }
35
}
36

37
long long query(int l, int r)
38
{
39
    long long ans = 0;
40
    if(pos[l] == pos[r])
41
    {
42
        for(int i = l;i <= r;i++)
43
        {
44
            ans += a[i] + b[pos[i]];
45
        }
46
        return ans;
47
    }
48
    for(int i = l;pos[i] == pos[l];i++)
49
    {
50
        ans += a[i] + b[pos[i]];
51
    }
52
    for(int i = pos[l] + 1;i <= pos[r] - 1;i++)
53
    {
54
        ans += blk[i];
55
    }
56
    for(int i = r;pos[i] == pos[r];i--)
57
    {
58
        ans += a[i] + b[pos[i]];
59
    }
60
    return ans;
61
}
62

63
int main()
64
{
65
    clock_t c1 = clock();
66
#ifdef LOCAL
67
    freopen("in.in", "r", stdin);
68
    freopen("out.out", "w", stdout);
69
#endif
70
    //------------------------------
71
    scanf("%d%d", &n, &m);
72
    R = sqrt(n) + 1;
73

74
    for(int i = 1;i <= n;i++)
75
    {
76
        scanf("%lld", &a[i]);
77
        pos[i] = i / R + 1;
78
        blk[pos[i]] += a[i];
79
    }
80
    long long opt, x, y, z;
81
    while(m--)
82
    {
83
        scanf("%lld", &opt);
84
        if(opt == 1)
85
        {
86
            scanf("%lld%lld%lld", &x, &y, &z);
87
            add(x, y, z);
88
        }
89
        else if(opt == 2)
90
        {
91
            scanf("%lld%lld", &x, &y);
92
            printf("%lld\n", query(x, y));
93
        }
94
    }
95

96

97

98
    //------------------------------
99
end:
100
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
101
    return 0;
102
}