题目链接：https://www.luogu.com.cn/problem/P1438
题意：输入一个数组a，支持两种操作：
1，在区间 [l , r]上加上首项为k，公差为d的数列，即a[l]上加k，a[l+1]上加k+d...a[r]上加k+(r-l)*d。
2，查询第p个数的值。
首先引出差分数组，即把原数组做差，比如1 3 4 7的差分数组（设为sub数组）为1 2 1 3。假设第一项前面有一个0，重要性质：
因此，对这题，用线段树维护差分数组的区间和即可，同时支持区间加。操作一时，更新sub[l]+=k , sub[i]+=d (l+1<=i<=r) , sub[r+1]-=k+(r-l)*d，操作二时，查询 [1 , p]的sub和即可得到a[p]。
AC code：
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=1e5+5; int n,m,a[maxn],sub[maxn]; int tr[maxn<<2],lz[maxn<<2]; void pushup(int u){ tr[u]=tr[u<<1]+tr[u<<1|1]; } void pushdown(int u,int l,int r){ int mid=(l+r)>>1; tr[u<<1]+=lz[u]*(mid-l+1); lz[u<<1]+=lz[u]; tr[u<<1|1]+=lz[u]*(r-mid); lz[u<<1|1]+=lz[u]; lz[u]=0; } void build(int u,int l,int r){ if(l==r){ tr[u]=sub[l]; return; } int mid=(l+r)>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } void update(int u,int l,int r,int L,int R,int v){ if(l>=L&&r<=R){ tr[u]+=v*(r-l+1); lz[u]+=v; return; } if(lz[u]) pushdown(u,l,r); int mid=(l+r)>>1; if(L<=mid) update(u<<1,l,mid,L,R,v); if(R>mid) update(u<<1|1,mid+1,r,L,R,v); pushup(u); } int query(int u,int l,int r,int L,int R){ if(l>=L&&r<=R){ return tr[u]; } if(lz[u]) pushdown(u,l,r); int ret=0,mid=(l+r)>>1; if(L<=mid) ret+=query(u<<1,l,mid,L,R); if(R>mid) ret+=query(u<<1|1,mid+1,r,L,R); pushup(u); return ret; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=n;++i) sub[i]=a[i]-a[i-1]; build(1,1,n); while(m--){ int op,l,r,k,d,p; scanf("%d",&op); if(op==1){ scanf("%d%d%d%d",&l,&r,&k,&d); update(1,1,n,l,l,k); if(r>l) update(1,1,n,l+1,r,d); if(r!=n) update(1,1,n,r+1,r+1,-k-(r-l)*d); } else{ scanf("%d",&p); printf("%d\n",query(1,1,n,1,p)); } } return 0; }
原文：https://www.cnblogs.com/FrankChen831X/p/12421387.html