給一個長為N的數列，有M次操作，每次操作是以下兩種之一： （1）修改數列中的一個數 （2）求數列中某連續一段的和 ...
- 總時間限制:
- 10000ms
- 單個測試點時間限制:
- 1000ms
- 記憶體限制:
- 262144kB
- 描述
-
給一個長為N的數列，有M次操作，每次操作是以下兩種之一：
（1）修改數列中的一個數
（2）求數列中某連續一段的和
- 輸入
- 第一行兩個正整數N和M。
第二行N個整數表示這個數列。
接下來M行，每行開頭是一個字元，若該字元為'M'，則表示一個修改操作，接下來兩個整數x和y，表示把x位置的值修改為y；若該字元為'Q'，則表示一個詢問操作，接下來兩個整數x和y，表示求[x,y]這段區間的和。 - 輸出
- 對每一個詢問操作單獨輸出一行，表示答案。
- 樣例輸入
-
5 3 1 2 3 4 5 Q 1 5 M 2 7 Q 1 5
- 樣例輸出
-
15 20
- 提示
- 1<=N<=10^5，1<=M<=10^5，輸入保證合法，且所有整數及答案可用帶符號32位整型存儲。
- 考慮樹狀數組肯定是沒有什麼疑問的，
- 但是這裡不是加減，而是直接修改，
- 然而直接修改會爆零，原因自己yy一下就知道。
- 所以說，我們每次改的時候，去加上要加的數和當前的數的差，然後再把當前的數改成將要改的數
-
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int MAXN=100001; 6 int a[MAXN]; 7 int tree[MAXN]; 8 int n,m; 9 void read(int &n) 10 { 11 char c='+';int x=0;bool flag=0; 12 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 13 while(c>='0'&&c<='9') 14 x=(x<<1)+(x<<3)+c-48,c=getchar(); 15 flag==1?n=-x:n=x; 16 } 17 int lb(int p) 18 { 19 return (p)&(-p); 20 } 21 void add(int pos,int v) 22 { 23 int p=pos; 24 while(p<=n) 25 { 26 tree[p]+=v; 27 p+=lb(p); 28 } 29 } 30 int sum(int pos) 31 { 32 int ans=0; 33 int p=pos; 34 while(p) 35 { 36 ans+=tree[p]; 37 p-=lb(p); 38 } 39 return ans; 40 } 41 int main() 42 { 43 read(n);read(m); 44 for(int i=1;i<=n;i++) 45 { 46 int p; 47 read(p); 48 a[i]=p; 49 add(i,p); 50 } 51 for(int i=1;i<=m;i++) 52 { 53 char c;int x,y; 54 cin>>c;read(x);read(y); 55 if(c=='Q') 56 printf("%d\n",sum(y)-sum(x-1)); 57 else 58 { 59 add(x,y-a[x]); 60 a[x]=y; 61 } 62 63 } 64 return 0; 65 }
