算法复习课堂笔记

---

一、一维差分

1. 核心定义

差分数组 c[i]：基于原数组 a 构建，满足

$$c[i] = a[i] - a[i-1]$$

2. 核心操作：区间快速修改

对原数组 a 的区间 [L, R] 内所有元素加 x，仅需对差分数组做两步操作：

• c[L] += x
• c[R+1] -= x

3. 还原原数组

通过差分数组 c 还原原数组 a（遍历累加即可）。

---

二、二维前缀和

1. 核心定义

二维前缀和数组 s[i][j]：表示原数组 a 前 i 行、前 j 列的总和。

2. 计算二维前缀和数组

公式：

$$s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j]$$

3. 子矩阵求和

若子矩阵左上角为 (x, y)，右下角为 (xx, yy)，则总和为：

$$s[xx][yy] - s[xx][y-1] - s[x-1][yy] + s[x-1][y-1]$$

---

三、二维差分

1. 核心定义

二维差分数组 c[i][j]：基于原数组 a 构建，满足

$$c[i][j] = a[i][j] + a[i-1][j-1] - a[i-1][j] - a[i][j-1]$$

2. 核心操作：子矩阵快速修改

对子矩阵（左上角 (x,y)，右下角 (xx,yy)）加 k，需对差分数组做四步操作：

• c[x][y] += k
• c[xx+1][yy+1] += k
• c[x][yy+1] -= k
• c[xx+1][y] -= k

3. 还原原数组

公式（类似二维前缀和逆过程）：

$$a[i][j] = c[i][j] + a[i][j-1] + a[i-1][j] - a[i-1][j-1]$$

---

四、并查集

1. 初始化

f[i] 存储第 i 个元素的“队长”，初始时每个元素独立为一个集合，自己是队长：

for (int i=1; i<=n; i++) f[i] = i;

2. 查找大队长（find 函数）

递归实现（带路径压缩优化，提升效率）：

int find(int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]); // 路径压缩：直接指向最终大队长
}

3. 判断是否同集合（pd 函数）

bool pd(int x, int y) {
    int rx = find(x), ry = find(y);
    return rx == ry; // 大队长相同则在同一集合
}

4. 合并集合（merger 函数）

void merger(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) {
        f[rx] = ry; // 将x集合的队长指向y集合的队长
    }
}