前缀和算法原理及代码

1.一维前缀和算法

• a.原数组{a[1], a[2], a[3], ..., a[n]}，注意：数组下标从1开始，同时令S[0] = 0。
• b.前缀和S[i]：S[i] = a[1] + a[2] + ... + a[i]
  • Q1：S[i]如何求出？
    • A1：for循环遍历一下原数组，其中S[i] = S[i-1] + a[i]
  • Q2：S[i]的作用？
    • A2：能够快速求出数组中任意一段范围内(如:[l, r])的和 ，即S[r] - S[l-1]

#include <iostream>

using namespace std;


const int N = 100010;

int n, m;
int a[N], s[N];

int main()
{
    scanf("%d%d", &n, &m);
    // 注意：原数组下标从1开始
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];  // 前缀和的初始化

    while(m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);  // 区间和的计算
    }
    return 0;
}

2.二维前缀和算法

• a.原二维数组{a[1][1], a[1][2], a[1][3], ..., a[n][m]}，注意：数组下标从1开始，同时令S[0][0] = 0。
• b.前缀和S[i][j]：S[i][j] = a[1][1] + a[1][2] + ... + a[i][j]
  • Q1：S[i][j]如何求出？
    • A1：for循环遍历一下原二维数组，其中S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j]
  • Q2：S[i][j]的作用？

    • A2：能够快速求出二维数组中任意一个子矩阵(如:{[i-1][j-1],[i][j]}的和 ，即S[i][j] - S[i-1][j-1]

      
      子矩阵的计算过程.png

#include <iostream>

using namespace std;


const int N = 1010;
int n, m, q;
int 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]);
    
    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];  // 求二维前缀和
    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;
}