09-进阶算法/01-前缀和与差分

前缀和

前缀和用于快速求区间和，预处理 [math]\displaystyle{ O(n) }[/math]，查询 [math]\displaystyle{ O(1) }[/math]。

一维前缀和

定义 [math]\displaystyle{ pre[i] = a[1] + a[2] + \cdots + a[i] }[/math]

区间 [math]\displaystyle{ [l, r] }[/math] 的和 = [math]\displaystyle{ pre[r] - pre[l-1] }[/math]

vector<int> a(n + 1), pre(n + 1);
for (int i = 1; i <= n; i++)
    pre[i] = pre[i - 1] + a[i];

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

二维前缀和

定义 [math]\displaystyle{ pre[i][j] }[/math] 为从 [math]\displaystyle{ (1,1) }[/math] 到 [math]\displaystyle{ (i,j) }[/math] 的矩阵和。

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];

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

差分

差分是前缀和的逆运算，用于快速进行区间修改。

一维差分

区间 [math]\displaystyle{ [l, r] }[/math] 加 [math]\displaystyle{ k }[/math]：

int diff[MAXN];

// 区间 [l, r] 加 k
diff[l] += k;
diff[r + 1] -= k;

// 最后求前缀和得到最终结果
for (int i = 1; i <= n; i++)
    diff[i] += diff[i - 1];

二维差分

子矩阵 [math]\displaystyle{ (x1,y1) }[/math] 到 [math]\displaystyle{ (x2,y2) }[/math] 加 [math]\displaystyle{ k }[/math]：

diff[x1][y1] += k;
diff[x2 + 1][y1] -= k;
diff[x1][y2 + 1] -= k;
diff[x2 + 1][y2 + 1] += k;

// 最后求二维前缀和得到最终结果