fenwick_tree.cpp

// // Binary Indexed Tree or Fenwick Tree
// // 1 based indexing of array
// #include <bits/stdc++.h>
// using namespace std;

// int sum(int k, int tree[]){
//     int s=0;
//     while(k>=1){
//         s+=tree[k];
//         k-=k&-k;
//     }
//     return s;
// }
// void add(int k,int x,int tree[],int n){
//     while(k<=n){
//         tree[k]+=x;
//         k+=k&-k;
//     }
// }

// int main() {
// 	int n;
// 	cin>>n;
// 	int arr[n+1],tree[n+1];
// 	arr[0]=0;
// 	memset(tree,0,sizeof(tree));
// 	for(int i=1;i<=n;i++){
// 	    cin>>arr[i];
// 	}
// 	for(int i=1;i<=n;i++){
// 	    add(i,arr[i],tree,n);
// 	}
// // 	for(int i=1;i<=n;i++){
// // 	    cout<<tree[i]<<" ";
// // 	}
// 	int q;
// // 	no of queries
// 	cin>>q;
// 	while(q--){
// 	    int type,a,b;
// 	    cin>>type>>a>>b;
// 	    if(type==1){
// 	       // range sum(a,b)
// 	       if(a==1){
// 	           cout<<sum(b,tree)<<"\n";
// 	       }
// 	       else{
// 	           cout<<sum(b,tree)-sum(a-1,tree)<<"\n";
// 	       }
// 	    }
// 	    else{
// 	       // Update arr[a]=b;
// 	       b-=arr[a];
// 	       add(a,b,tree,n);
// 	    }
// 	}
// 	return 0;
// }