差分数组

差分数组本质上来说就是一个数组，可以用 $O(1)$ 的时间处理区间修改。

设原数组为 $a$ 数组，差分数组为 $d$ 数组，则对于 $i\in[2,n]$，都有 $d[i]=a[i]-a[i-1]$。

性质：

  1. 更新区间 $[l, r]$ 时（区间加减运算），我们可以只更新 $d[l] += x, \quad d[r+1] -= x$
  2. 查询原数组 $a[i]$ 时，令 $S_n$ 为 $d[i]$ 的前缀和，那么 $a[i]=S[i]$
  3. 求原数组 $a[i]$ 的前缀和时，设前 $x$ 项的前缀和为 $sum_x$，则有：$$sum_x=\sum_{i=1}^{x}a[i]=\sum_{i=1}^{x}\sum_{j=1}^{i}d[j]=\sum_{i=1}^{x}(x-i+1)d[i]$$

例题

例1：Leetcode 2406. 将区间分为最少组数

[解析]：对于所有 intervals 区间组来说，如果有重叠我们将其分开，枚举所有的区间组，最高的重叠次数就是答案。从前往后枚举，用差分数组记录对应每个区间的计数，最后通过前缀和计算所有区间的最大计数即可（差分数组的前缀和 $Sum_d[i]$ 即为位置 $i$ 的重叠次数）。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        // 用 map 记录，防止a[i]的数组过大超内存
        // 不能用 unordered_map，因为我们统计时从小到大统计
        map<int, int> d;
        for (auto i : intervals) {
            d[i[0]]++;
            d[i[1]+1]--;
        }
        int res = 0, sum = 0;
        for (auto [_, v] : d) {
            res = max(res, sum += v);
        }
        return res;
    }
};

并查集

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

  • 合并（Union）：把两个不相交的集合合并为一个集合。
  • 查询（Find）：查询两个元素是否在同一个集合中。

进行多次合并和查询操作之后，根节点的个数即为集合的数量（fa[i] == i ）。

朴素的并查集

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

const int MAXN = 1e5+10;
int fa[MAXN];
void init(int n) {
	for (int i = 1; i <= n; i++) fa[i] = i;
}
int _find(int x) {
    return x == fa[x]? x: (fa[x] = _find(fa[x]));  // 路径压缩（注意赋值运算符 = 的优先级没有三元运算符 ?: 高，这里要加括号）
}
void merge(int i, int j) {
    int x = _find(i), y = _find(j);
    fa[y] = x;
}

“优化后”的并查集

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

const int MAXN = 1e5+10;
int fa[MAXN], rk[MAXN];
void init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i, rk[i] = 1;
}
int _find(int x) {
    return x == fa[x]? x: (fa[x] = _find(fa[x]));  // 路径压缩    
}
void merge(int i, int j) {
    int x = _find(i), y = _find(j);
    if (rk[x] <= rk[y]) fa[x] = y;  // 按秩合并
    else fa[y] = x;
    if (rk[x] == rk[y] && x != y) rk[y]++;  // 如果深度相同且根节点不同，则新的根节点的深度+1
}

注：优化后的并查集在合并时先调用_find进行了路径压缩，改变了树的秩，实际上路径压缩和按秩合并可以混用（不过此时秩失去了“子树高度”这个意义，但他的一些性质还是保留了下来）。不过大部分情况下按秩合并是一种负优化, 因为调整的代价过大，所以一般情况下推荐使用朴素的并查集。

例题

例1：Leetcode 剑指 Offer II 116. 省份数量

代码 
 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

class Solution {
public:
    int fa[205];
    void init(int n) {
        for (int i = 1; i <= n; i++) fa[i] = i;
    }
    int _find(int x) {
        return x==fa[x]? x: (fa[x] = _find(fa[x]));
    }
    void merge(int i, int j) {
        int x = _find(i), y = _find(j);
        fa[y] = x;
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        init(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j]) merge(i+1, j+1);
            }
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (fa[i] == i) ++cnt;
        }
        return cnt;
    }
};

例2：Leetcode 剑指 Offer II 118. 多余的边

[解析]：并查集查找第一个能形成环的边（加入该边会导致成环）。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int fa[1005];
    void init(int n) {
        for (int i = 1; i <= n; i++) fa[i] = i;
    }
    int _find(int x) {
        return x==fa[x]? x: (fa[x] = _find(fa[x]));
    }
    void merge(int i, int j) {
        int x = _find(i), y = _find(j);
        fa[y] = x;
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        init(n);
        for (auto v : edges) {
            if (_find(v[0]) != _find(v[1]))  merge(v[0], v[1]);
            else return v;
        }
        return vector<int>{};
    }
};

例3：Leetcode 1631. 最小体力消耗路径

[解析]：该题有多种解法，例如 DFS + 二分，Dijkstra 算法等，这里介绍使用并查集的思路。首先题目允许往任意方向移动，大概率排除 DP 的可能，从图论的方向思考：

  • 先把这张图存起来：边为所有上下左右相邻的顶点构成，边权是相邻顶点之间的高度差；

  • 假设整张图 m*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

class Solution {
public:
    int fa[10002];
    void init(int n) {
        for (int i = 0; i < n; i++) fa[i] = i;
    }
    int _find(int x) {
        return (x == fa[x])? x: (fa[x] = _find(fa[x]));
    }
    void merge(int i, int j) {
        int x = _find(i), y = _find(j);
        fa[y] = x;
    }

    vector<tuple<int, int, int>> G;
    int minimumEffortPath(vector<vector<int>>& heights) {
        int n = heights.size(), m = heights[0].size();
        // 建图
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int id = i * m + j;
                if (i > 0) G.emplace_back(id-m, id, abs(heights[i-1][j] - heights[i][j]));
                if (j > 0) G.emplace_back(id-1, id, abs(heights[i][j-1] - heights[i][j]));
            }
        }
        // 按权值从小到大排序
        sort(G.begin(), G.end(), [](const auto& t1, const auto& t2){
            auto&& [x1, y1, w1] = t1;
            auto&& [x2, y2, w2] = t2;
            return w1 < w2;
        });

        init(m*n);
        int res = 0;
        for (auto [x, y, w] : G) {
            if (_find(0) == _find(m * n - 1)) break;
            res = w;
            merge(x, y);
        }
        return res;
    }
};

树状数组

树状数组模版 

 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

const int N = 100;
int nums[N + 1]; // nums 是存放原始数据的数组
int bit[N + 1];  // bit 是树状数组，下标从 1 开始

int lowbit(int x) { return x & (-x); };

// 更新 nums[i] = x，这里不直接更新 nums，而是去更新 bit
void update(int i, int x) {
    while(i <= N) {
        bit[i] += x;
        i += lowbit(i);
    }
}

// 计算闭区间 [1, i] 的前缀和
int preSum(int i) {
    int res = 0;
    while(i > 0) {
        res += bit[i];
        i -= lowbit(i);
    }
    return res;
}

// 建立树状数组
void build(int n) {
    for (int i = 1; i <= n; i++) update(i, nums[i]);
}

int main() {
    for (int i = 0; i <= N; i++) nums[i] = i;
    build(N);
    cout << preSum(100) << endl;            // 5050
    cout << preSum(10) - preSum(5) << endl; // 40
    return 0;
}

单调栈

单调队列

最长上升子序列（LIS）