题目描述

Description

Input

第一行给出两个整数N，M。分别表示序列长度和操作个数
接下来一行有N个数，即给定的序列a1,a2,....an
接下来M行，每行对应一个操作，格式见题目描述

Output

对于每个询问操作，输出一行，表示所询问的SSi的值。

Sample Input

5 3
1 2 3 4 5
Query 5
Modify 3 2
Query 5

Sample Output

35
32

HINT

1<=N,M<=100000,且在任意时刻0<=Ai<=100000

题目分析

差分前缀和前缀和数列后 每次单点修改就相当于在这个位置~位置n加上了同一个数
线段树就好

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
long long val[100010],sum[100010];
char s[100];
struct your
{
    int x,y;
    long long sum,add;
}a[100010*4];
void build(int dx,int dy,int num)
{
    a[num].x=dx,a[num].y=dy;
    if(dx==dy) { a[num].sum=sum[dx]; return ; }
    int mid=(dx+dy)>>1;
    build(dx,mid,num<<1),build(mid+1,dy,num<<1|1);
    a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
}
void pushdown(int num)
{
    a[num<<1].sum+=(long long) (a[num<<1].y-a[num<<1].x+1)*a[num].add;
    a[num<<1|1].sum+=(long long) (a[num<<1|1].y-a[num<<1|1].x+1)*a[num].add;
    a[num<<1].add+=a[num].add,a[num<<1|1].add+=a[num].add;
    a[num].add=0;
}
void update(int dx,int dy,long long c,int num)
{
    if(a[num].x==dx&&a[num].y==dy)
    {
        a[num].sum+=(long long)c*(dy-dx+1);
        a[num].add+=c;
        return ;
    }
    if(a[num].add!=0) pushdown(num);
    int mid=(a[num].x+a[num].y)>>1;
    if(dy<=mid) update(dx,dy,c,num<<1);
    else if(dx>mid) update(dx,dy,c,num<<1|1);
    else update(dx,mid,c,num<<1),update(mid+1,dy,c,num<<1|1);
    a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
}
long long ask(int dx,int dy,int num)
{
    if(a[num].x==dx&&a[num].y==dy) return a[num].sum;
    if(a[num].add!=0) pushdown(num);
    int mid=(a[num].x+a[num].y)>>1;
    if(dy<=mid) return ask(dx,dy,num<<1);
    else if(dx>mid) return ask(dx,dy,num<<1|1);
    else return ask(dx,mid,num<<1)+ask(mid+1,dy,num<<1|1);
}
int main()
{   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&val[i]);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+val[i];
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+sum[i];
    for(int i=n;i>=1;i--) sum[i]=sum[i]-sum[i-1];
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        int x;
        long long c;
        scanf("%s",&s[0]);
        if(s[0]=='Q') scanf("%d",&x),printf("%lld\n",ask(1,x,1));
        else scanf("%d%lld",&x,&c),update(x,n,c-val[x],1),val[x]=c;
    }   
    return 0;

}