树状数组
2025-08-04 10:54:52
发布于:上海
15阅读
0回复
0点赞
就我老老实实用树状数组做的吗
#include<iostream>
using namespace std;
const int N=5e5+5;
int a,c[N],n,m;
int lowbit(int x){
return x & (-x);
}//求x二进制下的最低位的1的值 例如:lowbit(6)=2
void update(int x,int v){
while(x<=n){
c[x]+=v;
x+=lowbit(x);
}
}//单点修改(输入和改某个点的值都是这个)
int sum(int x){
int ans=0;
while(x>0){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}//区间求和(就是用树状数组模拟前缀和)
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a;
update(i,a);
}//输入
while(m--){
int op,x,y;
cin>>op>>x>>y;
if(op==1){//单点修改
update(x,y);
}else if(op==2){//求区间和
cout<<sum(y)-sum(x-1)<<"\n";
}
}
return 0;
}
这里空空如也
有帮助,赞一个