树状数组最基本应用吧
- //iOS::sync_with_stdio(false);
- #include<bits/stdc++.h>
- using namespace std;
- const int MAXN = 500010;
- int n,m;
- int C[MAXN];
- int lowbit(int x)
- {
- return x&-x;
- }
- void add(int i,int val)
- {
- while(i<=n){
- C[i]+=val;
- i +=lowbit(i);
- }
- }
- int sum(int i)
- {
- int s = 0;
- while(i>0){
- s+=C[i];
- i-=lowbit(i);
- }
- return s;
- }
- int main(){
- cin>> n>> m;
- int num1,num2,op;
- for(int i=1;i<=n;++i){
- cin>> num1;
- add(i,num1);
- }
- for(int i=0;i<m;++i){
- cin>> op>> num1>> num2;
- if(op==1){
- add(num1,num2);
- }
- else{
- cout << sum(num2) - sum(num1-1) <<endl;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2958435.html