题目链接：戳我
线段树中差分和前缀和的应用
其实对于加上等差数列的操作我们可以分成这样三步——
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,-(r-l)*d-k);
然后查询的时候1到当前位置的和就是这个数的值啦！
代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,m;
int a[MAXN];
struct Node{int l,r,sum,tag;}t[MAXN<<2];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void push_up(int x){t[x].sum=t[ls(x)].sum+t[rs(x)].sum;}
inline void solve(int x,int l,int r,int k)
{
t[x].tag+=k;
t[x].sum+=(r-l+1)*k;
}
inline void push_down(int x,int l,int r)
{
if(t[x].tag)
{
int mid=(l+r)>>1;
solve(ls(x),l,mid,t[x].tag);
solve(rs(x),mid+1,r,t[x].tag);
t[x].tag=0;
}
}
inline void update(int x,int l,int r,int ll,int rr,int k)
{
if(ll<=l&&r<=rr)
{
t[x].sum+=(r-l+1)*k;
t[x].tag+=k;
return;
}
int mid=(l+r)>>1;
push_down(x,l,r);
if(ll<=mid) update(ls(x),l,mid,ll,rr,k);
if(mid<rr) update(rs(x),mid+1,r,ll,rr,k);
push_up(x);
}
inline int query(int x,int l,int r,int ll,int rr)
{
int cur_ans=0;
if(ll<=l&&r<=rr) return t[x].sum;
int mid=(l+r)>>1;
push_down(x,l,r);
if(ll<=mid) cur_ans+=query(ls(x),l,mid,ll,rr);
if(mid<rr) cur_ans+=query(rs(x),mid+1,r,ll,rr);
return cur_ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
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,-(r-l)*d-k);
}
else
{
scanf("%d",&p);
printf("%d
",query(1,1,n,1,p)+a[p]);
}
}
return 0;
}
PS：（蒟蒻的一点小想法）
这道题让我们求的是单点查询。。。如果是区间查询呢？
这样我们就别用前缀和来表示这个数了，但是因为等差数列完全满足可加性，还是可以直接上线段树的啊！
下面是代码：（应该是没有什么问题，因为是在大佬的单点查询的代码基础上更改的）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 1100000
#define lson (now<<1)
#define rson (now<<1|1)
struct Node
{
int s,lyk,lyd;
void put(int now,int l,int r,int K,int D)
{
int la=(r-l)*D+K;
s+=(K+la)*(r-l+1)/2;
lyk+=K;
lyd+=D;
}
}t[MAX<<2];
int N,M;
int a[MAX];
void pushdown(int now,int l,int r)
{
if(!t[now].lyd&&!t[now].lyk)return;
int mid=(l+r)>>1;
t[lson].put(lson,l,mid,t[now].lyk,t[now].lyd);
t[rson].put(rson,mid+1,r,t[now].lyk+(mid-l+1)*t[now].lyd,t[now].lyd);
t[now].lyd=t[now].lyk=0;
}
void update(int now,int l,int r,int al,int ar,int K,int D)
{
pushdown(now,l,r);
if(l==al&&r==ar){t[now].put(now,l,r,K,D);}
else
{
int la=(ar-al)*D+K;
t[now].s+=(K+la)*(ar-al+1)/2;
int mid=(l+r)>>1;
if(ar<=mid)update(lson,l,mid,al,ar,K,D);
else if(al>mid)update(rson,mid+1,r,al,ar,K,D);
else
{
update(lson,l,mid,al,mid,K,D);
update(rson,mid+1,r,mid+1,ar,K+(mid+1-al)*D,D);
}
}
}
int query(int now,int l,int r,int ll,int rr)
{
int cur_ans=0;
pushdown(now,l,r);
if(ll<=l&&r<=rr) return t[now].s;
int mid=(l+r)>>1;
if(ll<=mid) cur_ans+=query(lson,l,mid,ll,rr);
if(mid<rr) cur_ans+=query(rson,mid+1,r,ll,rr);
return cur_ans;
}
int main()
{
freopen("ce.in","r",stdin);
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++) scanf("%d",&a[i]);
for(int i=1;i<=N;i++) a[i]+=a[i-1];
int opt;
while(M--)
{
scanf("%d",&opt);
if(opt==1)
{
int L,R,K,D;
scanf("%d%d%d%d",&L,&R,&K,&D);
update(1,1,N,L,R,K,D);
}
else
{
int p,q;
scanf("%d%d",&p,&q);
printf("%d
",query(1,1,N,p,q)+a[q]-a[p-1]);
}
}
return 0;
}