笔记
2025-09-21 12:02:41
发布于：浙江
5阅读
0回复
0点赞
前缀和与差分
解决的问题
现在有个数字,使用来表示。
并且有次提问，每一次提问求解范围，也就是第到第个数字总和为多少。
伪代码:
int a[MAXN] ;
int n;
cin >> n;
int q;
cin >> q;
for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
while(q -- ){
int l,r ; // 范围[l,r]
cin >> l >> r ;
int answer = 0 ; // 答案
for(int i = l ; i <= r ; i ++ ) answer += a[i]; // 让第l个数字累加到第r个数字
cout << answer << endl; // 输出答案
}
#include<bits/stdc++.h>
using namespace std;
int arr[1005];
int main(){
int n,m;
cin >> n >> m ; // 输入的数字总数和提问的次数
for(int i = 1 ; i <= n ; i ++ ) cin >> arr[i];
while(m -- ){
// 进行提问
int left,right ;
cin >> left >> right ; // 要求我们输出第left个数字到第right个数字的
// 数值总和
long long answer = 0 ; // 保存范围的数字总和
for(int i = left ; i <= right ; i ++ ){
answer += arr[i] ;
}
cout << answer << endl;
}
return 0;
}
这段代码固然可以解决这个问题，但是呢，如果我们的数字数量和提问次数，到达的级别，这时候，由于该段代码的时间复杂度为，最终计算次数可能会到达，而计算机在一秒当中计算的次数大约在次，因此这样写，会导致时间超限。
所以，我们要思考，有什么方法，可以让程序运行时间变短的同时，然后还能保证答案的正确性。
而这样的方法，我们会把他称之为算法。
前缀和
前缀和是通过创建范围1到任意数字的数值总和的数组，来解决这个问题的。
在这里，我们可以把这个数组称之为是sum数组, 因为它保存了从1到任意数字的数值总和。
for(int i = 1 ; i <= n ; i ++ ){
sum[i] = sum[i-1] + a[i]; // 构建第i个前缀和
}
当你需要求解范围的数值总和时，只需要计算sum[r]减去sum[l-1]即可。
int l,r ; // 范围[l,r]
cin >> l >> r ;
int answer = sum[r] - sum[l-1]; // 答案
// sum[r] - sum[l-1] 等价于 a[1] + a[2] +... + a[r] - a[1] - a[2] -... - a[l-1]
每一次求解范围数值，时间复杂度皆为，也就是一次减法即可，构建加单次查询的时间复杂度为，而前缀和的构建时间复杂度为，所以总的时间复杂度为。
参考代码
#include<bits/stdc++.h>
using namespace std;
int arr[100005];
int sum[100005];
int main(){
int n,m;
cin >> n >> m ; // 输入的数字总数和提问的次数
for(int i = 1 ; i <= n ; i ++ ) {
cin >> arr[i];
sum[i] = sum[i-1] + arr[i] ; // 构建前缀和数组
}
while(m -- ){
// 进行提问
int left,right ;
cin >> left >> right ; // 要求我们输出第left个数字到第right个数字的
cout << sum[right] - sum[left - 1] << endl;
// 通过前缀和求出范围总和
}
return 0;
}
差分
差分是前缀和的一种变形，它可以帮助我们解决一些区间加减的问题
模版
#include<bits/stdc++.h>
using namespace std;
// 1.统计两数之间的差值，保存 第一个数差值为本身
// a 1 2 2 1 2 1
// d 1 1 0 -1 1 -1
// 如果说，对d数组 差值数组进行前缀和，那么你可以还原原数组
// s -> d : 1 2 2 1 2 1
// 那么，如果对d数组进行修改后在进行前缀和呢？
// 比如，将d[1] +1,d[4] - 1
// d 2 1 0 -2 1 -1 -> 前缀和 : 2 3 3 1 2 1
// 刚好满足了[1,3]集体+1
// 对于差值建立一个数组，d[1]为a[1]本身
// 当需要对范围[l,r]进行区间+-，只需要把d[l] += 数值 ,
// d[r+1] -= 数值 即可完成区间修改
int a[1000005];
int d[1000005];
int main(){
int n,m;
cin >> n >> m ;
for(int i = 1 ; i <= n ; i ++ ){
cin >> a[i];
d[i] = a[i] - a[i-1];
}
while(m--){
int l,r,c;
cin >> l >> r >> c;
d[l] += c;
d[r+1] -= c;
}
int sum = 0 ;
for(int i = 1 ; i <= n ; i ++ ){
sum += d[i];
cout << sum << " " ;
}
return 0;
}
这里空空如也
有帮助，赞一个