解决单点更新的区间前缀和

#include <iostream>
#include <cmath>


#define int long long

using namespace std;
const int N=5e5+10;
int n,T,tree[N];
int lowbit(int i){
	return i&(-i);
}
//单点更新 找后继
void add(int id,int val){
	for(int i=id;i<=n;i=i+lowbit(i)){
		tree[i]+=val;
	}
}
//求前缀和 找前驱 
int presum(int st){
	int sum=0;
	//>=1不是0 
	for(int i=st;i>=1;i=i-lowbit(i)){
		sum+=tree[i];
	}
	return sum;
}
signed main(){
	cin>>n>>T;
	for(int i=1;i<=n;i++){
		int x;scanf("%lld",&x);
		add(i,x);
	} 
	while(T--){
		int opt,l,r;scanf("%lld %lld %lld",&opt,&l,&r);
		if(opt==1) add(l,r);
		else printf("%lld\n",presum(r)-presum(l-1));
	}
	return 0;
} 

时间复杂度：O(mlogn)