題目描述 如題,已知一個數列,你需要進行下麵兩種操作: 1.將某一個數加上x 2.求出某區間每一個數的和 輸入輸出格式 輸入格式: 第一行包含兩個整數N、M,分別表示該數列數字的個數和操作的總個數。 第二行包含N個用空格分隔的整數,其中第i個數字表示數列第i項的初始值。 接下來M行每行包含3或4個整 ...
題目描述
如題,已知一個數列,你需要進行下麵兩種操作:
1.將某一個數加上x
2.求出某區間每一個數的和
輸入輸出格式
輸入格式:第一行包含兩個整數N、M,分別表示該數列數字的個數和操作的總個數。
第二行包含N個用空格分隔的整數,其中第i個數字表示數列第i項的初始值。
接下來M行每行包含3或4個整數,表示一個操作,具體如下:
操作1: 格式:1 x k 含義:將第x個數加上k
操作2: 格式:2 x y 含義:輸出區間[x,y]內每個數的和
輸出格式:輸出包含若幹行整數,即為所有操作2的結果。
輸入輸出樣例
輸入樣例#1:5 5 1 5 4 2 3 1 1 3 2 2 5 1 3 -1 1 4 2 2 1 4輸出樣例#1:
14 16
說明
時空限制:1000ms,128M
數據規模:
對於30%的數據:N<=8,M<=10
對於70%的數據:N<=10000,M<=10000
對於100%的數據:N<=500000,M<=500000
樣例說明:
故輸出結果14、16
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int MAXN=500001; 6 int n,m,p; 7 int tree[MAXN];// 8 int lowbit(int p) 9 { 10 return p&(-p); 11 } 12 void point_increase(int w,int v) 13 { 14 for(int i=w;i<=n;i=i+lowbit(i)) 15 tree[i]=tree[i]+v; 16 return ; 17 }//將增加的值加到每一個管理點上 18 int interval_ask(int x) 19 { 20 int ans=0; 21 for(int i=x;i!=0;i=i-lowbit(i)) 22 ans=ans+tree[i]; 23 return ans; 24 }//求出一個首碼和並返回 25 int main() 26 { 27 scanf("%d%d",&n,&m); 28 for(int i=1;i<=n;i++) 29 { 30 scanf("%d",&p); 31 point_increase(i,p); 32 }// 將每一個點初始化為管理自身的管理點 33 for(int i=1;i<=m;i++) 34 { 35 scanf("%d",&p); 36 if(p==1)// 加 37 { 38 int x,y; 39 scanf("%d%d",&x,&y); 40 point_increase(x,y); 41 } 42 else// 求和 43 { 44 int x,y; 45 scanf("%d%d",&x,&y); 46 printf("%d\n",interval_ask(y)-interval_ask(x-1)); 47 }//因為樹狀數組只能求首碼和所以需要兩區間相加 48 } 49 return 0; 50 }