前缀和

贡献者：有机物

　　前缀和算法分为一维和二维，一维前缀和可以很快速的求序列中某一段的和。而二维前缀和可以快速求一个矩阵中某个子矩阵的和（以下讲的是以 $x_{1}, y_{1}$ 为左上角， $x_{2}, y_{2}$ 为右下角的子矩阵）。

1. 一维前缀和

　　一维前缀和的朴素做法是一个 for 循环求和，时间复杂度为： $O (n \times m)$ 。 $m$ 为询问次数。

　　而前缀和的时间复杂度为：预处理 $O (n)$ ，查询 $O (m)$ 。

　　一维前缀和：

\begin{matrix} (1) & \sum_{i = l}^{r} a_{i}, \end{matrix}

　　预处理：

\begin{matrix} (2) & S_{i} = \sum_{k = 1}^{i} a_{k} . \end{matrix}

　　如何预处理？

\begin{matrix} (3) & ∵ \sum_{k = 1}^{i} a_{k} - \sum_{k = 1}^{i - 1} a_{k} = a_{k} ∴ \sum_{k = 1}^{i} a_{k} = \sum_{k = 1}^{i - 1} a_{k} + a_{k}, \end{matrix}

　　即：

\begin{matrix} (4) & S_{k} - S_{k - 1} = a_{k} S_{k} = S_{k - 1} + a_{k} . \end{matrix}

　　如何求答案？

\begin{matrix} (5) & \sum_{i = l}^{r} a_{i} = \sum_{i = 1}^{r} a_{i} - \sum_{i = 1}^{l - 1} a_{i} = S_{r} - S_{l - 1} . \end{matrix}

　　还有要注意的是 $S_{0} = 0$ ，因为如果想求 $1 \sim n$ 一段数的和可以直接输出 $S_{10} - S_{0} = S_{10}$ 。因此可以从下标为 $1$ 开始存数，这样就不需要做复杂的处理。

　　 朴素代码

const int N = 100010;
int a[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    
    while (m -- )
    {
        int l, r;
        cin >> l >> r;
        
        int res = 0;
        for (int i = l; i <= r; i ++ ) res += a[i];
        cout << res << endl;
    }
    
    return 0;
}

　　 前缀和

const int N = 100010;
int n, m, a[N], s[N];

int main() 
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
    
    while (m -- )
    {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;    // 前缀和公式，O(1)
    }
    
    return 0;
}

2. 二维前缀和

　　二维前缀和的朴素做法是两重循环暴力求和。时间复杂度为： $O (q \times n m)$ 。 $q$ 为询问次数， $n$ 、 $m$ 为矩阵大小。

　　而二维前缀和的时间复杂度为 $O (n \times m)$

　　二维前缀和：

\begin{matrix} (6) & \sum_{i = x 1}^{x 2} \sum_{j = y 1}^{y 2} a_{i j}, \end{matrix}

　　预处理：

\begin{matrix} (7) & S_{i j} = \sum_{k_{1} = 1}^{i} \sum_{k_{2} = 1}^{j} a_{k_{1} k_{2}} . \end{matrix}

　　如何预处理？

　　在预处理 $S_{i j}$ 时，要注意 $S_{i - 1, m}$ 和 $S_{i, j - 1}$ 都已经被算过了，因为预处理是逐行逐列来计算的（重复地方不重复计算）。

\begin{matrix} (8) & S_{i j} = \sum_{k_{1} = 1}^{i} \sum_{k_{2} = 1}^{j} a_{k_{1} k_{2}} = \sum_{k_{1} = 1}^{i - 1} \sum_{k_{2} = 1}^{j} + \sum_{k_{1} = 1}^{i} \sum_{k_{2} = 1}^{j - 1} - \sum_{k_{1} = 1}^{i - 1} \sum_{k_{2} = 1}^{j - 1} + a_{i, j}, \end{matrix}

　　即：

\begin{matrix} (9) & S_{i, j} = S_{i - 1, j} + S_{i, j - 1} - S_{i - 1, j - 1} + a_{i, j} . \end{matrix}

　　如何求答案？

\begin{matrix} (10) & \sum_{i = x_{1}}^{x_{2}} \sum_{j = y_{1}}^{y_{2}} a_{i j} = \sum_{k_{1} = 1}^{x_{2}} \sum_{k_{2} = 1}^{y_{2}} a_{k_{1} k_{2}} - \sum_{k_{1} = 1}^{x_{1} - 1} \sum_{k_{2} = 1}^{y_{2}} a_{k_{1} k_{2}} - \sum_{k_{1} = 1}^{x_{2}} \sum_{k_{2} = 1}^{y_{1} - 1} a_{k_{1} k_{2}} + \sum_{k_{1} = 1}^{x_{1} - 1} \sum_{k_{2} = 1}^{y_{1} - 1} a_{k_{1} k_{2}}, \end{matrix}

　　即：

\begin{matrix} (11) & S_{x_{2}, y_{2}} - S_{x_{1} - 1, y_{2}} - S_{x_{2}, y_{1} - 1} + S_{x_{1} - 1, y_{1} - 1} . \end{matrix}

　　二维前缀和可能有点抽象，可以根据几张图片来对二维前缀和有个更好的理解。

图 1：预处理

1

图 2：预处理

2

图 3：预处理

3

图 4：预处理

4

图 5：预处理

5

图 6：预处理

6

　　求前缀和的公式类似推导预处理的过程。

　　 朴素代码

const int N = 1010;
int n, m, q, a[N][N], s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);
    
    while (q -- ) 
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        
        int res = 0;
        for (int i = x1; i <= x2; i ++ )
            for (int j = y1; j <= y2; j ++ )
                res += a[i][j];
        
        cout << res << endl;
    }
    
    return 0;
}

　　二维前缀和代码：

const int N = 1010;
int n, m, q, a[N][N], s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] 
            - s[i - 1][j - 1] + a[i][j];    // 预处理公式
        }
        
    while (q -- )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", 
        s[x2][y2] - s[x1 - 1][y2] 
        - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);  // 前缀和公式
    }
    
    return 0;
}

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。