BZOJ3155:Preprefix sum(线段树)

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

Solution

直接用线段树维护一次前缀和的数组$S$，然后修改后缀，查询前缀。注意常数。

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define N (100009)

 #define LL long long

 using namespace std;

 struct Sgt{LL val,add;}Segt[N<<];

 int n,m,x,y;

 LL a[N],S[N];

 char opt[];

 inline int read()

 {

     int x=; char c=getchar();

     while (c<'' || c>'') c=getchar();

     while (c>='' && c<='') x=x*+c-'', c=getchar();

     return x;

 }

 void Pushdown(int now,int l,int r)

 {

     if (Segt[now].add)

     {

         int mid=(l+r)>>;

         Segt[now<<].add+=Segt[now].add;

         Segt[now<<|].add+=Segt[now].add;

         Segt[now<<].val+=Segt[now].add*(mid-l+);

         Segt[now<<|].val+=Segt[now].add*(r-mid);

         Segt[now].add=;

     }

 }

 void Update(int now,int l,int r,int l1,int r1,LL k)

 {

     if (l>r1|| r<l1) return;

     if (l1<=l && r<=r1)

     {

         Segt[now].add+=k;

         Segt[now].val+=(r-l+)*k;

         return;

     }

     int mid=(l+r)>>; Pushdown(now,l,r);

     Update(now<<,l,mid,l1,r1,k);

     Update(now<<|,mid+,r,l1,r1,k);

     Segt[now].val=Segt[now<<].val+Segt[now<<|].val;

 }

 LL Query(int now,int l,int r,int l1,int r1)

 {

     if (l>r1|| r<l1) return ;

     if (l1<=l && r<=r1) return Segt[now].val;

     int mid=(l+r)>>; Pushdown(now,l,r);

     return Query(now<<,l,mid,l1,r1)+Query(now<<|,mid+,r,l1,r1);

 }

 int main()

 {

     n=read(); m=read();

     for (int i=; i<=n; ++i)

         a[i]=read(), S[i]=S[i-]+a[i], Update(,,n,i,i,S[i]);

     while (m--)

     {

         scanf("%s",&opt); x=read();

         if (opt[]=='Q') printf("%lld\n",Query(,,n,,x));

         else y=read(), Update(,,n,x,n,y-a[x]), a[x]=y;

     }

 }

巴特西