网站 手机 微信 app,福建网站开发企业,项目网络计划软件教程,网站制作公司知道万维科技前缀和
前缀和的作用#xff1a;快速计算数组中某一段区间内的总和
1.需要两个额外的数组#xff0c;来存储原始数据的数组 和 计算过前缀的数组。其原理为前缀和的数组中每个元素用来保存前i个原数组中的和#xff0c;下一个元素更新就采用s[i] s[i] - 1 a [i] 来持续更… 前缀和
前缀和的作用快速计算数组中某一段区间内的总和
1.需要两个额外的数组来存储原始数据的数组 和 计算过前缀的数组。其原理为前缀和的数组中每个元素用来保存前i个原数组中的和下一个元素更新就采用s[i] s[i] - 1 a [i] 来持续更新当前的元素。
2.首先需要对前缀和数组s进行初始化s[0] 默认初始化为 0 从1开始进行初始化。
3.计算原数组中L到R某一段区间 可以直接使用s[R] - s[L - 1]。
#include iostreamusing namespace std;const int N 100010;int n, m;
int a[N], s[N];int main()
{scanf(%d%d, n, m);for (int i 1; i n; i ) scanf(%d, a[i]);//s[0] 0 for (int i 1; i n; i ) s[i] s[i - 1] a[i]; // 前缀和的初始化while (m -- ){int l, r;scanf(%d%d, l, r);printf(%d\n, s[r] - s[l - 1]); // 区间和的计算}return 0;
}差分
1.提供两个数组数组a为前缀和数组数组b为差分数组可以通过b推出a. O(n)
2.差分为前缀和的逆运算
3.作用差分使用O(1)的时间给原数组中的某个区间都同意加上同一个数。
#include iostream
using namespace std;const int N 100010;int n , m;int a[N],b[N];void insert(int l, int r , int c)
{b[l] c;b[r 1] - c;
}int main()
{scanf(%d%d,a, m);for(int i 1; i n ; i) scanf(%d,a[i]);for(int i 1 ; i n; i) insert(i,i,a[i]);while(m--){int l , r , c;scanf(%d%d%d,l,r,c);insert(l,r,c);}for(int i 1; i n; i) b[i] b[i - 1];for(int i 1; in ;i)printf(%d ,b[i]);return 0;}
