例 输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。如果暴力遍历，时间复杂度为O(m*n) 可能超时
则采用前缀和算法并查询
a[N]记得是从1开始,a[0]=0, 因为如果是求（1，r) 需要sum[r]-sum[0]

[前缀和] [c++]
1
2
3
4
5
6
7
8
9
10
11
const int N = 1e5 + 10;
int sum[N], a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
for(int i = 1;i <= n; i++)
{ 
    sum[i] = sum[i - 1] + a[i];   //前缀和的初始化
}
while(m--)
{
    cin>>l>>r;
    cout<<sum[r] - sum[l - 1];
}

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
二维前缀和思路相同 但是要推导公式

[二维前缀和] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N];s[N][M];
int main()
{
    cin>>n>>m>>q;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin>>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;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1])<<endl; //算子矩阵的和
    }
    return 0;
}

一维差分类似于数学中的求导和积分，差分可以看成前缀和的逆运算
首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];
然后我们构造一个数组b ： b[1], b[2], b[3],,,,,, b[i];
使得 a[i] = b[1] + b[2] + b[3] + ,,,,,, + b[i]
也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。

例
输入一个长度为n的整数序列。
接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。
请你输出进行完所有操作后的序列。

[一维差分] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N],n,m; 
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}

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

二维思路相似

[二维差分] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            insert(i, j, i, j, a[i][j]);      //其实也不能算构造 差分数组创建的时候就直接行了
        }
    }
    while (q--)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];  //二维前缀和
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            printf("%d ", b[i][j]);
        }
        printf("\n");
    }
    return 0;
}

acwing 3729
这道题一开始想的区间合并 听了讲解发现居然能差分
因为每个位置的数只会增加 所以只要操作次数不是0 那么值就为1
怎么记录操作次数呢 就需要用差分
b[1]到b[i]的前缀和就是第i个元素的操作次数 极大节省时间
差分数组不用刻意去构造 创建的时候就能直接弄出来

[3729] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
long long n,mid;
const int N=2e5+10;
long long b[N];
void add(int l,int r)
	{
		b[l]+=1;
		b[r+1]-=1;
	}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long t;
	cin>>t;

	while(t--)
	{
		int n;
		cin>>n;
		memset(b,0,sizeof b);
		for(int i=1;i<=n;i++)
		{
		    int x;
			cin>>x;
			if(x==0) continue;
			else if(x>=i) add(1,i);
			else add(i-x+1,i);
		}
		for(int i=1;i<=n;i++) b[i]+=b[i-1]; //此时b[i]存的是操作次数
		
		for(int i=1;i<=n;i++)
		{
		    if(b[i]!=0) cout<<1<<" ";
		    else cout<<0<<" ";
		}
		cout<<endl;
	
	}
    
	return 0;
}