前缀和与差分

1. 一维前缀和

在学习前缀和之前，我们先来看一个题目，了解前缀和的用处。

链接: 题目链接

题目描述

给定一个数组a，有q次询问，对于每次询问：给定两个数 l，r。求第l个数到第r个数的和。

输入描述

第一行一个整数表示样例个数T，1<=T<=10 。
对于每组样例：
第一行两个整数n,q, 分别表示数组长度和询问次数。1<=n,q<=1e5.
第二行n个整数，表示数组a，-1e9<=ai<=1e9.
接下来q行，每行两个整数l,r 表示询问的区间。

输出描述

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

输入样例

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

输出样例

3
14
7
8
26

暴力解法：
对于每一次询问，遍历区间进行求和，时间复杂度为O(T* n*q)，最大为1e11，所以暴力必然超时。

改变思路，用前缀和，对于每一次询问都可以通过O(1)的复杂度实现。

实现方法：再开一个数组pre，用来保存a数组的前 i 项和。
即：pre[i]=pre[i-1]+a[i];
要求 l - r 区间的和即求 : pre[r]-pre[l-1]；

话不多说，上代码

一维前缀和

//2024 jin
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll a[N], pre[N];//记得开ll ，int会爆
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		int n, q;
		cin >> n >> q;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			//前缀和
			pre[i] = pre[i - 1] + a[i];
		}
		while (q--)
		{
			int l, r;
			cin >> l >> r;
			cout << pre[r] - pre[l - 1] << '\n';
		}
	}
	return 0;
}

2.一维差分

首先来介绍一下差分数组（diff），diff[i]=a[i]-a[i-1]，差分与前缀和的区别就是一个是减，一个是加。

由上面一维前缀和我们了解到前缀和可以快速求出一个区间的和。接下来我们看看差分有哪些妙用。

1.还原成a[i]：对差分数组进行前缀和能还原出a[i]。
2.区间修改：差分数组能够快速的对区间进行修改，时间复杂度为O(1)。

接下来看一个题目
链接: 题目链接

题目描述

给定一个长度为n的数组a，和两个整数p,q。
先进行p次区间加操作：将区间[l,r]的数字都加上x。
再进行q次区间查询操作：求出[l,r]的数字之和。
对于每次区间查询操作，输出结果。

输入描述

第一行三个整数

标签：pre,前缀,int,差分,数组,diff
From： https://www.cnblogs.com/jin1/p/18627802