前缀和-差分笔记
2026-07-04 11:39:12
发布于：广东
8阅读
0回复
0点赞
//前缀和 -->前缀的和
//动态规划
//1.记忆化 ?记忆答案，确定数组要存储一个怎样的答案
//2.状态转移方程 ? 已知推导未知
int pre[N];//pre[i]--[1,i]所有数据的和
1 2 3 4 5 6 7 8
pre[1]=1;
pre[2]=3;
pre[3]=6=1+2+3;
pre[4]=10=pre[3]+a[4];
pre[i]=pre[i-1]+a[i];
[l,r]? 求解区间和
pre[r] [1,r],多计算了[1,l-1]
pre[r]-pre[l-1];
//https://www.acgo.cn/problemset/info/336?homeworkId=21694&teamCode=1989649572886384640
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
ll pre[N];
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];//
}
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
//https://www.acgo.cn/problemset/info/29345?homeworkId=21694&teamCode=1989649572886384640
//对于给定的[l,r] t=(1奇数，2偶数)
//第一步操作要使得l,r,t情况要么全部是奇数，要么全部是偶数
//通过改变l（++）和r（--）
//if(l%2!=t%2)l++;
//if(r%2!=t%2)r--;
//最终对于x=r-l+1,答案为(x+1)/2;
//https://www.acgo.cn/problemset/info/83451?homeworkId=21694&teamCode=1989649572886384640
//对于任意一对相邻且相等的位置i和i+1
//贡献全部放在i+1的位置上
//aabbcc 对应的贡献数组为
//010101 //贡献放右边
//对于区间[l,r]的答案也不能去直接求解[l,r]的和
//比如说[2,3]的答案应该为0，但是区间和为1
//观察发现对于2的位置贡献不应该加上
//所以对于区间[l,r]的答案只需要去计算[l+1,r]的区间和即可
// https://www.acgo.cn/problemset/info/29752?homeworkId=21694&teamCode=1989649572886384640
//差分 --->前缀和
//[l,r] +x
//1 2 3 4 5
//0 0 0 0 0
//2 2 2 0 0 [1,3] +2;
//2 5 5 2 0 [2,4] +3;
//前缀和
//1 2 3 4 5
//0 0 0 0 0
//1 0 0 0 0 //在此基础计算前缀和数组
//1 1 1 1 1 //目标[1,4]+1
//1 0 0 0 -1 //初始数组
//1 1 1 1 0 //前缀和数组，实现[1,4]+1;
// //将区间[2,4] +5
//0 5 0 0 -5;
//0 5 5 5 0
//[l,r] +x;
//a[N];
//a[l]+x;
//a[r+1]-x;
//所有的操作结束之后
//求pre数组，对应pre[i]表示的就是i的位置需要增加多少
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
ll pre[N];
void solve(){
int n,p;
cin>>n>>p;
for(int i=1;i<=n;i++)cin>>a[i];
while(p--){
int l,r,x;
cin>>l>>r>>x;
pre[l]+=x;
pre[r+1]-=x;
}
//操作结束之后求前缀和就能够知道每个位置对应需要加多少
for(int i=1;i<=n;i++){
pre[i]+=pre[i-1];
a[i]+=pre[i];;//对于每个位置需要加的值加上。
}
sort(a+1,a+n+1);
cout<<a[1]<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
这里空空如也
有帮助，赞一个