Fenwick Tree

Input

The first line of input contains two integers NN, QQ, where 1≤N≤50000001≤N≤5000000 is the length of the array and 0≤Q≤50000000≤Q≤5000000 is the number of operations. Then follow QQ lines giving the operations. There are two types of operations:

• “+ ii δδ” indicates that a[i]a[i] is incremented by δδ, where 0≤i<N0≤i<N and −109≤δ≤109−109≤δ≤109 (both are integers)

• “? ii” is a query for the value of a[0]+a[1]+…+a[i−1]a[0]+a[1]+…+a[i−1], where 0≤i≤N0≤i≤N (for i=0i=0 this is interpreted as an empty sum)

Output

For each query in the input, output one line giving the answer to that query.

10 4
+ 7 23
? 8
+ 3 17
? 8

23
40

5 4
+ 0 -43
+ 4 1
? 0
? 5

0
-42

题意

N个数，Q个询问，+i表示a[i] +一个数，？i表示询问a[0] ~ a[i-1]的和

思路

放上树状数组模板

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN =  ;
int N,Tree[MAXN];
#define LL long long
LL a[MAXN];
LL lowbit(LL p) { return (p&-p); }
LL sum(LL p) {
    LL ret = ;
    while (p> ) ret+=a[p], p-=lowbit(p);
    return ret;
}
void add(LL p, LL v) { // 若要减去，则v传入一个负数
    while (p <= N) a[p]+=v, p+=lowbit(p);
}
int main(){
    while(cin>>N){
    int t;
    cin>>t;
    memset(Tree,,sizeof(Tree));
    for(int i=;i<=t;i++){
        char ch;
        int a,b;
        cin>>ch;
        if(ch=='+'){
            cin>>a>>b;
            add(a+,b);
        }
        else{
            cin>>a;
            cout<<sum(a)<<endl;
        }
    }
}
    return ;
}