分块

分块是个很有意思的维护数据的思想。通常可以用于维护线段树等数据结构难以维护的信息。

典型的分块思路

我们把整个序列分成大小为 BB 的 n/Bn/B 个块。

对于一个修改操作 [l,r][l,r]：

  • 如果 [l,r][l,r] 在同一个块内，我们直接遍历 [l,r][l,r] 进行暴力修改。单次的复杂度是 O(B)O(B) 的；
  • 如果跨越多个块，我们把 [l,r][l,r] 分解成若干个整块和最多两个散块，修改整块时，我们只 O(1)O(1) 修改整块上的 tag，而修改散块时则直接暴力。单次的复杂度是 O(n/B+B)O(n/B+B) 的

对于查询 [l,r][l,r]：

  • 如果在同一个块内，我们先下放这个块上的 tag 并更新序列，然后直接遍历求解，复杂度是 O(B)O(B) 的
  • 如果跨越了多个块，那么我们还是先拆成多个整块和最多两个散块，对于散块，我们还是先下放 tag 然后暴力，这一部分是 O(B)O(B) 的；对于整块，我们不下放 tag，而是带着 tag 在块上进行查询（这一步通常需要维护额外的信息，这些信息会需要在修改散块的时候趁机更新），一般的话，可以做到 O(1)O(1) 查询一个整块，那么单次的时间复杂度就是 O(n/B+B)O(n/B+B)

分块例题

CF121E. Lucky Array

我们发现要“维护 4,7,44,…4,7,44,\dots 等特殊数字的个数”这个任务很难用线段树操作，所以转而尝试分块。假设块长为 BB，分了 n/Bn/B 块。

因为 ai≤104a_i\le 10^4 且这样的 lucky number 的数量只有 3030 多个，所以我们在块上开 10410^4 个桶记录值域，即 bucket[v]=∣{i:ai=v}∣\text{bucket}[v]=|\{ i: a_i=v \}|

这里还有区间加的操作，我们在块上维护 tag 表示区间累计加了多少，查询 lucky number 个数的时候相应减去即可。时间复杂度 O(nn),B=nO(n\sqrt n),B=\sqrt n

Code

带着 tag 查询 lucky number 的时候需要注意 value >= tag 这个问题，不然数组会越界。

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
103
104
105
106
107
108
109
110
111
#include <bits/extc++.h>
#include <bits/stdc++.h>
constexpr int N = 1e5 + 10;
constexpr int V = 1e4 + 10;
constexpr int B = 400;

std::vector<int> P;
int ck[V];
int n, m;
int a[N];
int L[B], R[B], belong[N], bsize, bnum;
int map[B][V], tag[B];

void init_ck() {
    for (int b = 1; b <= 4; b++) {
        for (int i = 0; i < (1 << b); i++) {
            int t = 0;
            for (int j = 0; j < b; j++) {
                if (i & (1 << j)) t = t * 10 + 4;
                else t = t * 10 + 7;
            }
            if (t < V) {
                ck[t] = 1;
                P.push_back(t);
            }
        }
    }
}
int check(int x) { return ck[x]; }

void rebuild(int l, int r, int v) {
    int id = belong[l];
    if (tag[id] == 0) {
        if (v == 0) return;
        for (int i = l; i <= r; i++) {
            map[id][a[i]]--;
            a[i] += v;
            map[id][a[i]]++;
        }
    } else {
        for (int i = L[id]; i <= R[id]; i++) {
            map[id][a[i]]--;
            a[i] += tag[id];
            if (l <= i && i <= r) a[i] += v;
            map[id][a[i]]++;
        }
        tag[id] = 0;
    }
}

void add(int l, int r, int v) {
    int s = belong[l], e = belong[r];
    if (s == e) rebuild(l, r, v);
    else {
        rebuild(l, R[s], v);
        rebuild(L[e], r, v);
        for (int i = s + 1; i < e; i++) tag[i] += v;
    }
}

int query(int l, int r) {
    int s = belong[l], e = belong[r];
    int ans = 0;
    if (s == e) {
        rebuild(l, r, 0);
        for (int i = l; i <= r; i++) ans += ck[a[i]];
    } else {
        rebuild(l, R[s], 0);
        rebuild(L[e], r, 0);
        for (int i = l; i <= R[s]; i++) ans += ck[a[i]];
        for (int i = L[e]; i <= r; i++) ans += ck[a[i]];
        for (int i = s + 1; i < e; i++) {
            for (int p : P)
                if (p >= tag[i]) ans += map[i][p - tag[i]];
        }
    }
    return ans;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::cout.tie(nullptr);

    init_ck();

    std::cin >> n >> m;
    bsize = std::sqrt(P.size() * n);
    bnum  = (n + bsize - 1) / bsize;
    for (int i = 1; i <= bnum; i++) {
        L[i] = (i - 1) * bsize + 1;
        R[i] = std::min(i * bsize, n);
        for (int j = L[i]; j <= R[i]; j++) belong[j] = i;
    }

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        map[belong[i]][a[i]]++;
    }

    std::string op;
    int l, r, v;
    while (m--) {
        std::cin >> op >> l >> r;
        if (op == "add") {
            std::cin >> v;
            add(l, r, v);
        } else {
            std::cout << query(l, r) << '\n';
        }
    }
}

根号分治