前缀和和差分

一维前缀和

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int N = 100010;
 5 int n,m;
 6 int a[N],s[N]; //初始化s[0] = 0
 7 
 8 int main()
 9 {
10     scanf("%d%d", &n, &m);
11     for (int i = 1; i <= n; i ++ ) cin >> a[i];
12     
13     for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; //前缀和读入(公式)初始化
14     
15     while (m -- ) // m次读入
16     {
17         int l,r;
18         scanf("%d%d", &l, &r);
19         printf("%d\n",s[r] - s[l - 1]);//部分前缀和
20     }
21     return 0;
22 }

二维前缀和

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int N = 1010;
 5 int n,m,q;
 6 int a[N][N],s[N][N];
 7 
 8 int main()
 9 {
10     scanf("%d%d%d", &n, &m,&q);
11     for(int i = 1;i <= n; i ++)
12        for(int j = 1;j <= m; j ++)
13         scanf("%d", &a[i][j]);
14         
15     for(int i = 1; i <= n; i ++)
16        for(int j = 1; j <= m ; j ++)
17         s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; //求前缀和
18     
19     while(q -- )
20     {
21         int x1,y1,x2,y2;
22         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
23         printf("%d\n",s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);//算子矩阵的合
24     }
25     return 0;
26 }

S[i,j]S[i,j]即为图1红框中所有数的的和为：

S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]
(x1,y1),(x2,y2)(x1,y1),(x2,y2)这一子矩阵中的所有数之和为：S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,