当前位置：首页 > news >正文

前缀和与差分（一维）

news 2024/9/20 5:03:02

一维前缀和与一维差分

一维前缀和

假如我们需要求一个数组的[L,R]这个区间的区间和，假如说我们要访问q次，我们能想到的就是暴力的去计算每一组的和，这样的时间复杂度为O(n*q)假如我们的q和n非常大那么这个时间复杂度是不太行的，所以我们要用到前缀和数组
在这里插入图片描述
我们现在知道前缀和数组存储的是[0,R]区间的和，那么我们怎么得到[L,R]区间的和呢？我们发现可以让[0,R]的区间和减去[0,L]的区间和

代码如下

#include<iostream>
using namespace std;
const int N = 5;
int sum[N];
//#define get_sum(L,R) (L?sum[R]-sum[L-1]:sum[R])
int get_sum(int L, int R)
{if (L != 0){return sum[R] - sum[L - 1];}return sum[R];
}
int main()
{int n = 5;int arr[N] = { 1,3,5,7,2 };sum[0] = arr[0];for (int i = 1; i < n; i++){sum[i] = sum[i - 1] + arr[i];}for (int i = 0; i < n; i++){cout << sum[i] << " ";}cout << endl;cout << get_sum(0, 3) << endl;cout << get_sum(2, 4) << endl;return 0;
}

一维前缀和模板

sum[0] = arr[0];
for (int i = 1; i < n; i++)
{sum[i] = sum[i - 1] + arr[i];
}

一维差分

给定一个n个数的数组arr[1,3,7,5,2] 我们需要m个操作需要在区间[L,R]中每一个数都加上val,最后询问数组arr中的元素是怎样的？
在这里插入图片描述
我们遍历数组的每一个元素然后每遍历一次就加上对应的数值此时时间复杂度为O(n*m),那如何去优化呢？

我们可以看到对与下标为2的数7他被操作了三次其最后结果其实就是7+(5+2-4)=10就是7+3=10，那我们是不是可以把中间的过程省略呢？

在这里插入图片描述
我们着重要记住差分标记

我们根据上面的差分标记来试着操作一下

我们发现把标记后的差分数组，进行一次前缀和操作，可以得到最终的答案。
为什么会这样呢？
我们来看一下下图

这就是差分标记的由来。那么使用差分后时间复杂度是多少呢，为O(n+m)是一个线性的复杂度。

代码如下

#include<iostream>
using namespace std;int d[6] = { 0 };// 定义一个差分数组，长度为6（比原数组多1），并初始化为0。额外的1位是为了防止后续操作越界。// 实现对区间 [l, r] 进行加值操作
void add(int l, int r, int val)
{d[l] += val;     // 在位置 l 增加 val，表示从这个位置开始增加 vald[r + 1] -= val; // 在位置 r+1 减少 val，表示从 r+1 之后开始不再增加 val
}int main()
{// 定义初始数组 arr，内容为 {1, 3, 7, 5, 2}int arr[] = { 1,3,7,5,2 };// 对区间 [2, 4] 的元素增加 5add(2, 4, 5);// 对区间 [1, 3] 的元素增加 2add(1, 3, 2);// 对区间 [0, 2] 的元素减少 4add(0, 2, -4);// 遍历原数组，构建前缀和，将差分数组的变化累加到 d 数组中for (int i = 0; i < 5; i++){d[i] += d[i - 1]; // 将前一个位置的差分值累加到当前 d[i] 上，形成最终影响}// 将差分数组 d 的累加结果应用到原数组 arr 上，并输出修改后的数组for (int i = 0; i < 5; i++){arr[i] += d[i];    // 将差分值加到原数组上cout << arr[i] << " "; // 输出修改后的数组元素}// 将差分数组 d 置为 0，防止后续影响，但此处的 memset 用法有误，应为 sizeof(d) 而不是 sizeof(0)memset(d, 0, sizeof(d));return 0;
}