洛谷傳送門

題目描述

前綴和（prefix sum）𝑆𝑖=。

前前綴和（preprefix sum）則把?𝑆𝑖 作為原序列再進行前綴和。記再次求得前綴和第?𝑖?個是?𝑆𝑆𝑖。

給一個長度?𝑛?的序列?𝑎1,𝑎2,??,𝑎𝑛有兩種操作：

1. Modify i x：把?𝑎𝑖 改成?𝑥。
2. Query i：查詢?𝑆𝑆𝑖。

輸入格式

第一行給出兩個整數?𝑁,𝑀。分別表示序列長度和操作個數。
接下來一行有?𝑁?個數，即給定的序列?𝑎1,𝑎2,??,𝑎𝑛?。
接下來?𝑀?行，每行對應一個操作，格式見題目描述。

輸出格式

對于每個詢問操作，輸出一行，表示所詢問的?𝑆𝑆𝑖?的值。

輸入輸出樣例

輸入

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

輸出?

35
32

說明/提示

1≤𝑁,𝑀≤1e5，且在任意時刻?0≤𝐴𝑖≤1e5。

題目解讀

? ? ? ? 由題意知，題目的意思就是求前綴和的前綴和，下面是一個酣暢淋漓的數學推理

數學推理

? ? ? ? 舉個例子:

? ? ? ? ?

//對于   1 2 3 4 5
//   a[]=1 2 3 4 5
//s[1]=1
//s[2]=1+2
//s[3]=1+2+3
//s[4]=1+2+3+4
//s[5]=1+2+3+4+5
//ss[5]=s[1]+s[2]+s[3]+s[4]+s[5]
//     =1*5++2*(5-1)+3*(5-2)+4*(5-3)+5*(5-4)

?

? ? ? ? 依此類推，我們可以發現==

方法

? ? ? ? 我們用兩個樹狀數組 c 與 c1，分別維護( k 為常數不管)，

Code

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+5;
long long n,m,a[N],c[N],c1[N],id[N],ni[N];
long long lowbit(long long x){return (-x)&x;}
void add(long long x,long long y){for(;x<=n+1;x+=lowbit(x))c[x]+=y;}//將 c[x] 加上 y
void add1(long long x,long long y){for(;x<=n+1;x+=lowbit(x))c1[x]+=y;}//將 c1[x] 加上 y
long long sum(long long x){//求 c 的前綴和long long ret=0;for(;x;x-=lowbit(x))ret+=c[x];return ret;
}
long long sum1(long long x){//求 c1 的前綴和long long ret=0;for(;x;x-=lowbit(x))ret+=c1[x];return ret;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];add(i,a[i]-0);add1(i,(i-1)*(a[i]-0));//分別向 c 和 c1 加入 a[i] 和 (i-1)*a[i]}string t;int x,y;for(int i=1;i<=m;i++){cin>>t;if(t=="Query"){cin>>x;cout<<x*sum(x)-sum1(x)<<'\n';//輸出結果}else{cin>>x>>y;add(x,y-a[x]);add1(x,(x-1)*(y-a[x]));//修改a[x]=y;}}return 0;
}