Preprocessing.md

预处理

1 前缀和

前缀和是一种常用的预处理技术，用于快速计算数组中某个区间内所有元素的和。

基本思想

通过预处理构建一个前缀和数组，实现​​区间和​​的快速查询。

一维前缀和

• 定义： $sum[i] = a[1] + a[2] + ... + a[i]$
• 时间复杂度：
  • 预处理： $O(n)$
  • 查询： $O(1)$
• 空间复杂度： $O(n)$

// 预处理一维前缀和
for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] + a[i];
}

// 查询区间 [l, r] 的和
int result = sum[r] - sum[l - 1];

二维前缀和

• 定义： $sum[i][j]$ 表示以 $(1, 1)$ 为左上角， $(i, j)$ 为右下角的子矩阵元素和。
• 时间复杂度：
  • 预处理： $O(nm)$
  • 查询： $O(1)$
• 空间复杂度： $O(nm)$

// 预处理二维前缀和
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
    }
}

// 查询子矩阵 [(x1,y1), (x2,y2)] 的和
int result = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];

2 差分

差分是前缀和的逆运算，用于快速对数组的某个区间进行修改操作。

基本思想

通过构建差分数组，将​​区间增减操作​​转化为端点修改。

一维差分

• 定义： $b[i] = a[i] - a[i - 1]$
• 时间复杂度：
  • 预处理： $O(n)$
  • 修改： $O(1)$
  • 还原： $O(n)$
• 空间复杂度： $O(n)$

// 构造差分数组
for (int i = 1; i <= n; i++) {
    b[i] = a[i] - a[i - 1];
}

// 对区间 [l, r] 加上常数 c
b[l] += c;
b[r + 1] -= c;

// 通过差分数组还原原数组
for (int i = 1; i <= n; i++) {
    a[i] = a[i - 1] + b[i];
}

二维差分

• 定义： $b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]$
• 时间复杂度：
  • 预处理： $O(nm)$
  • 修改： $O(1)$
  • 还原： $O(nm)$
• 空间复杂度： $O(nm)$

// 构造二维差分数组
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
    }
}

// 对子矩阵 [(x1,y1), (x2,y2)] 加上常数 c
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;

// 通过二维差分数组还原原数组
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];
    }
}