前缀和与差分

前缀和公式为 num[i] = num[i - 1] + a[i] 差分公式为 diff[i] = a[i] - a[i - 1] 前缀和与差分是能互相转换的 前缀和数组进行一次差分可得原数组 差分数组进行前缀和可得原数组

原数组 ---前缀和---> 前缀和数组 前缀和数组 ---差分---> 原数组 原数组 ---差分---> 差分数组 差分数组---前缀和---> 原数组

前缀和数组 <----> 原数组 <---> 差分数组

一维前缀和 题目描述 给定义一个数组𝑎，有𝑞+1次询问，对于每次询问： 给定两个整数𝑙,𝑟，求出𝑎𝑙 + 𝑎𝑙+1 + ... + 𝑎𝑟的结果。

输入描述 第一行一个整数表示样例个数T(1≤T≤10)。 对于每组样例： 第一行2个整数n(1≤n≤10^5),q(1≤q≤10^5)，分别表示数组长度和询问次数。

第二行n个整数，表示数组a(−10^9≤ai≤10^9)。

接下来q行，每行两个整数r(1≤l≤r≤n)表示询问的区间。

输出描述 对于每组样例，一行一个整数表示答案。

输入样例1 2 5 3 1 2 3 4 5 1 2 2 5 3 4 7 2 -1 9 -10 8 2 6 11 1 5 2 7 输出样例1 3 14 7 8 26

题解 根据输入的数组，建立一个每次相加前一位的数组 如输入的为1 2 3 4 5 根据前缀进行和 1，1+2=3，3+3=6，6+4=10，10+5=15 建立的数组为1 3 6 10 15 对于查询的区间（l,r）只需进行算出：r位减去（l-1）位之间的值即可 如查询（2,5）之间的和，15-1即是（2,5）区间的和

代码样例

#include<iostream>
#include<vector>
using namespace std;
using ll = long long;
void vol() {
	ll m, n; cin >> m >> n;
	vector<ll>ve(m + 1 , 0);
	for (ll i = 1; i <= m; i++) {
		cin >> ve[i];
	}
	vector<ll>cop(m + 1, 0);
	for (ll i = 1; i <= m; i++) {
		cop[i] = cop[i - 1] + ve[i];
	}
	ll l, r;
	for (ll i = 1; i <= n; i++) {
		cin >> l >> r;
		cout << cop[r] - cop[l - 1] << '\n';
	}
}
int main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t; cin >> t;
	while (t--) {
		vol();
	}
	return 0;
}

一维差分 题目描述 给定一个长度为n的数组a，和两个整数p,q。 先进行p次区间加操作：将区间[l,r]的数字都加上x。

再进行q次区间查询操作：求出[l,r]的数字之和。 对于每次区间查询操作，输出结果。 输入描述 第一行三个整数n,p,q。(1≤n≤10^5 ,0≤p≤10^5 ,0≤10^5 ≤q)

第二行n个整数表示数组a。(−10^9 ≤ai ≤10^9 )

接下来p行，每行三个整数l,r,x。(1≤l≤r≤n,−10^9 ≤x≤10^9 )

接下来q行，每行两个整数(1≤l≤r≤n)

输出描述 对于每次区间查询操作，输出结果。

输入样例1 5 1 2 1 1 1 2 2 1 4 2 1 3 1 5 输出样例1 9 15

题解 根据输入的数组建立一个差分数组 如输入1,2,3,4,5 1-0=1，2-1=1，3-2=1，4-3=1，5-4=1 因此建立的差分数组为1,1,1,1,1

代码实例

#include<iostream>
using namespace std;
const int N = 1e5+9;
using ll = long long;
ll a[N], diff[N], num[N];
int main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n , p , q ; cin >> n >> p >> q ;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) diff[i] = a[i] - a[i - 1];
	
	while (p--) {
		ll l, r, x; cin >> l >> r >> x;
		diff[l] += x; diff[r + 1] -= x;
	}

	for (int i = 1; i <= n; i++) a[i] = diff[i] + a[i - 1];
	for (int i = 1; i <= n; i++) num[i] = num[i - 1] + a[i];
	
	while (q--) {
		ll l, r; cin >> l >> r;
		cout << num[r] - num[l - 1] << '\n';
	}

	return 0;
}

二维前缀和 二维数组基本原理与一维前缀和几乎相同 注意重叠部分即可

题目描述 给定一个n行m列的整数矩阵。 q个询问，每个询问格式为：x1,y1,x2,y2，表示一个子矩阵的左上角和右下角的坐标。 对于每个询问，请回答子矩阵的所有数之和。

输入格式 第一行包括三个整数n,m,q（1≤n,m≤10^3 ，1≤𝑞≤10^5,1≤q≤10^5 ）。 接下来n行，每行包括m个整数，表示整数矩阵（每个整数的取值范围为[1,10^5 ]）。 接下来q行，每行包括四个整数x1,y1,x2,y2(1<=x1<=x2<=n,1<=y1<=y2<=m)，表示一个询问的左上角、右下角坐标。

输出格式 共q行，第i（1≤i≤q）行输出第i个询问的结果。

样例输入1 7 3 2 3 5 1 6 2 4 7 9 10 4 3 6 3 9 9 6 10 1 9 10 4 2 2 7 3 2 1 4 2 样例输出1 77 31

代码实例

#include<iostream>
#include<vector>
using namespace std;
using ll = long long;

int main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll n, m, q; cin >> n >> m >> q;
	vector<vector<ll> >a(n + 1, vector < ll >(m + 1, 0));
	ll i, j;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	vector<vector<ll> >b(n + 1, vector < ll >(m + 1, 0));
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			b[i][j] = b[i - 1][j] + b[i][j - 1] + a[i][j] - b[i - 1][j - 1];
		}
	}
	
	while (q--) {
		ll x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1] << '\n';
	}

	return 0;
}

二维差分 题目描述 给定一个n行m列的整数矩阵。 有q个操作，每个操作格式为：x1,y1,x2,y2,c，其中(𝑥1,𝑦1)、(x2,y2) 分别表示一个子矩阵的左上角和右下角的坐标，每个操作将对应的子矩阵的每个元素加上c。

请输出进行完所有操作后的矩阵。

输入描述 第一行包括三个整数n,m,q（1≤n,m≤10^3 ,1≤q≤10^5 ）。

输出描述 共n行，每行包括m个整数，表示进行完所有操作后的矩阵。

输入样例1 4 3 3 1 5 1 3 3 2 5 3 4 4 4 2 1 2 1 2 2 2 1 2 3 2 4 2 4 3 1 输出样例1 1 7 1 5 5 4 5 3 4 4 5 3

代码示例

//二维差分
#include<iostream>
using namespace std;
using ll = long long;
const int N = 1e3 + 9;

ll a[N][N], diff[N][N];

int main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	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++) {
			diff[i][j] += a[i][j];
			diff[i + 1][j] -= a[i][j];
			diff[i][j + 1] -= a[i][j];
			diff[i + 1][j + 1] += a[i][j];
		}
	}
	//修改
	while (q--) {
		int x1, y1, x2, y2, c;
		cin >> x1 >> y1 >> x2 >> y2 >> c;
		diff[x1][y1] += c; 
		diff[x2 + 1][y2 + 1] += c;
		diff[x2 + 1][y1] -= c;
		diff[x1][y2 + 1] -= c;
	}
	//求原数组
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + diff[i][j];
			cout << a[i][j] << " ";
		}
		cout << '\n';
	}

	return 0;
}