本笔记内容来源于算法基础课

前缀和

对于给定的数组$a_1, a_2, … , a_n$

则前缀和数组为$s_1, s_2, …, s_n$, 其中$s_i = a_1 + a_2 + … + a_i$，$s_0 = 0$

求$s_i$

s[0] = 0;
for (int i = 1; i <= n ; i++) {
    s[i] = s[i - 1] + a[i];
}

$s_i$作用

前缀和能快速地求解数组中一段数的和

求数组中任意区间[l, r]的和：

1. 遍历区间数组，时间复杂度为$O(n)$
2. $s_r - s_{l-1}$, 时间复杂度为$O(1)$

$s_0 = 0$是为了定义的统一如$s_1 = s_0 + a_1$，求[1, 10]$s_{10} - s_0$

注意：

边界问题

二维前缀和

将数组扩展到二维$s_{ij} = \sum\limits_{x=1 \sim i, y=1 \sim j}a_{xy}$

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

作用：能快速地求解二维矩阵中任意个子矩阵以$(x_1, y_1)$ $(x_2, y_2)$为对角线顶点的和
$s_{x_{2}, y_{2}} - s_{x_{1}-1, y_{2}} - s_{x_{2}, y_{1}-1} + s_{x_{1}-1, y_{1}-1} $

后缀和

对于给定的数组$a_1, a_2, … , a_n$

则后缀和数组为$s_1, s_2, …, s_n$, 其中$s_i = a_i + a_{i+1} + … + a_n$，$s_{n+1} = 0$

s[n+1] = 0;
for (int i = n; i >= 1; i--) {
    s[i] = s[i + 1] + a[i]
}

作用也是能快速地求解数组中任意区间[l, r]的和,$s_l - s_{r+1}$, 求[1, 10]$s_{1} - s_{9}$