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.
Sample Input 1 | Sample Output 1 |
---|---|
10 4 + 7 23 ? 8 + 3 17 ? 8 |
23 40 |
Sample Input 2 | Sample Output 2 |
---|---|
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 = 5000010 ; int N,Tree[MAXN]; #define LL long long LL a[MAXN]; LL lowbit(LL p) { return (p&-p); } LL sum(LL p) { LL ret = 0; while (p> 0) 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,0,sizeof(Tree)); for(int i=1;i<=t;i++){ char ch; int a,b; cin>>ch; if(ch=='+'){ cin>>a>>b; add(a+1,b); } else{ cin>>a; cout<<sum(a)<<endl; } } } return 0; }