前缀和

贡献者： 有机物

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

1. 一维前缀和

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

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

　　 一维前缀和：

　　 预处理：

　　 如何预处理？

　　 即：

　　 如何求答案？

　　 还有要注意的是 $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. 二维前缀和

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

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

　　 二维前缀和：

　　 预处理：

　　 如何预处理？

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

　　 即：

　　 如何求答案？

　　 即：

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

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

　　 朴素代码

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;
}