关于前缀和和差分的理解应用

yuanshen77 / 2023-08-13 / 原文

前缀和和差分是互相正逆运用的产物。2023-08-13 00:30:28

1.一维前缀和

令 a 数组 b[i] 代表 b[1]+b[2]+b[3]+…+b[i]

Q：问 b[l] 到 b[r] 的和

A: O（n），核心步骤：

在读取b每步都记录 a[i] = b[i]+a[i-1]，最后只要输出 a[r+1] - a[l]

以下为代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 int a[100005],b[100005],n,m,l,r;
 5 int main()
 6 {
 7     cin>>n>>m;
 8     for(int i = 1 ; i <= n ; i++)
 9     {
10         cin>>b[i];
11         a[i]=a[i-1]+b[i];
12     }
13     while(m--)
14     {
15         cin>>l>>r;
16         cout<<a[r]-a[l-1]<<"\n";
17     }
18     return 0;
19 }

2.二维前缀和

令 a 数组例如a[2][3] 代表 b[1][1]+b[2][1]+b[1][2]+b[2][2]+b[1][3]+b[2][3];

Q：问 b[x1][y1] 到 b[x2][y2] 的和

A : O(NM)，核心步骤：

a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j] 最后 ans = a[x2][y2] - a[x2][y1-1]-a[x1-1][y2] + a[x1-1][y1-1]

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[1005][1005],s[1005][1005],n,m,xo,yo,xs,ys,q;
int main()
{
    cin>>n>>m>>q;
    for(int i = 1 ; i <= n ; i++ )
        for(int j = 1 ; j <= m ; j++)
        {
            cin>>a[i][j];
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    while(q--) {
       cin>>xo>>yo>>xs>>ys;
       ll ans = s[ys][xs]-s[yo-1][xs]-s[yo-1][ys]+s[yo-1][xo-1];
       cout<<ans<<"\n";
    }
    return 0;
}

3.一维差分

令 a 数组 a[i] 代表 b[1]+b[2]+b[3]+…+b[i]

Q： 如果我们想令从 a[l] 到 a[r] 的值全部加上c(常数)；

A: 暴力循环只能是TLE，但是通过核心步骤：

b[i]+=c , b[r+1] - = c;

实现O（1）解决

以下是代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 ll a[10005],b[10005],l,r,c,n,q;
 5 void insert(int l , int r , int c)
 6 {
 7     b[l]+=c;
 8     b[r+1]-=c;
 9 }
10 int main()
11 {
12     cin>>n>>q;
13     for(int i = 1 ; i <= n ; i++)
14     {
15         cin>>a[i];
16         insert(i,i,a[i]);
17     }
18     while(q--)
19     {
20         cin>>l>>r>>c;
21         insert(l,r,c);
22     }
23     //前缀和操作
24     for(int i = 1 ; i <= n ; i++)
25     {
26         a[i]=a[i-1]+b[i];
27         cout<<a[i]<<" ";
28     }
29 
30     return 0;

4.二维差分

令 a 数组例如a[2][3] 代表 b[1][1]+b[2][1]+b[1][2]+b[2][2]+b[1][3]+b[2][3];

Q : 如果我们想从a[x1][y1] 到 a[x2][y2] 的值全部加上 c（常数）

A : 暴力循环是 O(NM)，核心步骤是：

b[x1][y1]+=c

b[x1][y1+1]-=c

b[x2][y2+1]-=c

b[x2+1][y2+1]+=c

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 ll a[1005][1005],b[1005][1005],c,x,y,x2,y2,n,m,q;
 5 
 6 void insert(int x,int y, int x2, int y2,int c)
 7 {
 8     b[x][y] += c;
 9     b[x][y2+1] -= c;
10     b[x2+1][y] -= c;
11     b[x2+1][y2+1] += c;
12 }
13 
14 int main()
15 {
16     cin>>n>>m>>q;
17     for(int i = 1 ; i <= n ; i++)
18         for(int j = 1 ; j <= m ; j++)
19         {
20             cin>>a[i][j];
21             insert(i,j,i,j,a[i][j]);
22         }
23     while(q--)
24     {
25        cin>>x>>y>>x2>>y2>>c;
26         insert(x,y,x2,y2,c);
27     }
28     for(int i = 1 ; i <= n ; i++) {
29         for (int j = 1; j <= m; j++) {
30             a[i][j] = b[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
31             cout << a[i][j] << " ";
32         }
33         cout << "\n";
34     }
35     return 0;
36 }