本文包含「数据结构」类型题中的：线段树、树状数组、并查集等。持续更新中。
题目描述：
方法1：
方法2：
方法3：
坑点：
线段树
将区间 \([1,n]\) 逐层二分成子区间（总数不超过 \(4n\)），从而实现对区间 \([L,R]\) 的 \(O(\log 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
| const int N = 1e5;
struct node {
int l, r, sum;
};
vector<node> tree(N);
vector<int> nums;
void build(int id, int l, int r){
tree[id].l = l;
tree[id].r = r;
if(l == r){
tree[id].sum = nums[l];
return;
}
int mid = (l + r) >> 1;
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
tree[id].sum = tree[2 * id].sum + tree[2 * id + 1].sum;
return;
}
int search(int id, int l, int r){
if(tree[id].l >= l && tree[id].r <= r)
return tree[id].sum;
if(tree[id].r < l || tree[id].l > r)
return 0;
int s = 0;
if(tree[2 * id].r >= l)
s += search(2 * id, l, r);
if(tree[2 * id + 1].l <= r)
s += search(2 * id + 1, l, r);
return s;
}
void change(int id, int i, int k){
if(tree[id].l == i && tree[id].r == i){
tree[id].sum = k;
return;
}
int mid = (tree[id].l + tree[id].r) >> 1;
if(i <= mid)
change(2 * id, i, k);
else
change(2 * id + 1, i, k);
tree[id].sum = tree[2 * id].sum + tree[2 * id + 1].sum;
return;
}
NumArray(vector<int>& num) {
nums = num;
build(1, 0, num.size() - 1);
}
void update(int index, int val) {
change(1, index, val);
}
int sumRange(int left, int right) {
return search(1, left, right);
}
|
307. 区域和检索 - 数组可修改 (H)
题目描述：给定一个数组，要求实现两个操作：单点更新、区间和查询。
方法1：分块，
方法2：线段树，
方法3：树状数组，
2407. 最长递增子序列 II (H)
题目描述：一个整数数组 nums，找到其中最长严格递增子序列的长度，要求子序列中相邻元素的差值不超过 k。
方法1：DP，定义 \(dp[i]\) 为以 \(nums[i]\) 结尾的 LIS 长度，每次从 \(dp[j]\) 中找满足条件的最大值转移，复杂度 \(O(n^2)\)。 \[ dp[i]=\max (dp[j])+1 \text {, 其中 } 0 \leq j<i \text { 且 } num[i]-k\leqslant num[j]<num[i] \] 方法2：DP + 线段树，定义 \(dp[i]\) 为以 \(i\) 结尾的 LIS 长度，用线段树表示 \(dp\) 数组，在区间内查询最大值，然后更新目标值、更新区间最大值。复杂度 \(O(n \log n)\)。 \[ dp[nums[i]]=\max (dp[j])+1 \text {, 其中 } num[i]-k \leq j<num[i] \]
树状数组
线段树更适合区间修改问题，单点修改问题建议用树状数组。使用时要注意，下标从 1 开始。
单点修改，求区间和模板：
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
| long long tree[30050];
vector<int> num;
int n;
int lowbit(int x) {
return x & -x;
}
long long query(int x) {
long long ans = 0;
for(int i = x; i > 0; i -= lowbit(i))
ans += tree[i];
return ans;
}
void add(int x, int u) {
for(int i = x; i <= n; i += lowbit(i))
tree[i] += u;
}
NumArray(vector<int>& nums) {
num = nums;
memset(tree, 0, sizeof(tree));
n = nums.size();
for(int i = 1; i <= n; i++){
add(i, nums[i - 1]);
}
}
void update(int index, int val) {
add(index + 1, val - num[index]);
num[index] = val;
}
long long sumRange(int left, int right) {
return query(right + 1) - query(left);
}
|
单点修改，求最值模板：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| long long tree[100050];
long long dp[100050];
int n;
int lowbit(int x) {
return x & -x;
}
long long query(int x, int y){
long long ans = 0;
while(y >= x){
ans = max(dp[y], ans);
y--;
for(; y - lowbit(y) >= x; y -= lowbit(y))
ans = max(tree[y], ans);
}
return ans;
}
void update(int x, long long u) {
for(int i = x; i <= n; i += lowbit(i))
tree[i] = max(u, tree[i]);
}
|
并查集
并查集主要用于处理不相交集合的合并问题，常用于快速判断两个点是否在同一个集合。在使用路径压缩优化后，合并和查找操作都近似 \(O(1)\) 时间复杂度。
并查集极简模板（在函数内定义即可）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int fa[n], size[n], setCnt = n;
iota(fa, fa + n, 0);
fill(size, size + n, 1);
function<int(int)> find = [&](int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
};
auto merge = [&](int from, int to){
from = find(from);
to = find(to);
if (from != to) {
fa[from] = to;
size[to] += size[from];
setCnt--;
}
};
|
并查集完整类模板：
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
| class UnionFind {
public:
vector<int> parent;
vector<int> size;
int n;
int setCount;
public:
UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
--setCount;
return true;
}
bool connected(int x, int y) {
x = find(x);
y = find(y);
return x == y;
}
};
|
相关题目：
1971. 寻找图中是否存在路径 (E)
题目描述：给定一张具有 \(n\) 个顶点的双向图，判断是否存在从顶点 A 到顶点 B 的有效路径。
方法1：BFS，建图后，将顶点 A 先放入队列，每次将其邻居入队，直到队列为空或访问到顶点 B 时结束。时空复杂度均为 \(O(n+m)\)。
方法2：DFS，建图后，从顶点 A 开始递归搜索，用 \(vis\) 记忆每个访问过的顶点防止陷入循环，遍历完所有邻居后如果还没访问到 B，则返回 false。时空复杂度均为 \(O(n+m)\)。
方法3：并查集，将图中每个连通分量视为一个集合，用并查集维护，判断 A 和 B 是否属于一个集合即可。空间复杂度 \(O(n)\)，时间复杂度 \(O(n+m)\)。
547. 省份数量 (M)
题目描述：有 \(n\) 个城市，其中一些彼此相连，用一个邻接矩阵存储。省份是一组直接或间接相连的城市，求省份数量。
方法1：DFS，使用 \(vis\) 数组记录访问过的城市，以每个未访问的城市为起点开始搜索，并标记访问。搜索起点的个数就是省份数量。时间复杂度 \(O(n)\)。
方法2：并查集，维护集合数 \(cntSet\)，合并每个相连的城市，最后的 \(cntSet\) 就是答案。时间复杂度 \(O(n)\)。
684. 冗余连接 (M)
题目描述：给定往一棵 \(n\) 个节点的树中添加一条边后的图，从中找出一条可删去的边，删除后可使得剩余部分恢复成树，如果有多个答案，返回数组 edges 中最后出现的边。
方法1：并查集，最后出现的边就是第一个导致环的边，起初每个点属于不同的连通分量，遍历每条边将节点相连。如果某一条边的两端顶点已经属于同一个集合，则说明它就是冗余边。时间复杂度 \(O(n)\)。
399. 除法求值 (H)
题目描述：给定一个字符串分式数组和分式的浮点数值，再给出一组查询分式数组，要求根据已知条件计算出值，如果没有答案则返回 -1.0。
变量之间的倍数关系具有传递性，因此可以看作图论问题，分子和分母各为图中的节点，分式的值作为两点之间的权重。要查询到分式首先要判断分子与分母是否有联系，有联系才可能计算出结果。
由于分子、分母本身是字符串，如果要建图，就需要用哈希表将每个出现过的字符串映射成数字索引，用连续的数字表示节点编号。
方法1：BFS，建图后，对于每个查询，从起点出发，通过 BFS 的方式，不断更新起点与当前点之间的路径长度，直到搜索到终点为止。
方法2：Floyd 算法，对于查询数量很多的情形，如果为每次查询都独立搜索一次，则效率会变低。可以使用 Floyd 算法，预先计算出任意两点之间的距离。
方法3：带权并查集，不需要建图，用哈希表维护并查集。只需将出现过的分子、分母放到同一个集合，即可快速判断两个字符串是否有联系。并查集同时维护每个字符串到其父节点的倍数，路径压缩、合并时也要更新倍数。每次查询时只需判断是否在同一个集合，再将其通分成同一个祖先的倍数相除即可。