树状数组的基本操作:修改某个数(维护区间),求区间和
①修改(给第x个数加c)
void add(int x,int c)
{
w[x]+=c;
for(int i=x;i<=n;i+=lowbit(i))
tr[i]+=c;
}
②求区间和 (1~x的区间和)
若求[a,b]区间和,则为sum(b)-sum(a-1)
int sum(int x)
{
int res=0;
for(int i=x;i>=1;i-=lowbit(i))
res+=tr[i];
return res;
}
整体代码:(注意使用add(i,w[i])初始化树状数组)
#include<iostream>
using namespace std;
const int N=1e5+5;
int w[N];
int tr[N];
int n,m;
int lowbit(int x)
{
return x&-x;
}
int sum(int x)
{
int res=0;
for(int i=x;i>=1;i-=lowbit(i))
res+=tr[i];
return res;
}
void add(int x,int c)
{
w[x]+=c;
for(int i=x;i<=n;i+=lowbit(i))
tr[i]+=c;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>w[i],add(i,w[i]);
while(m--)
{
int k,a,b;cin>>k>>a>>b;
if(!k) cout<<sum(b)-sum(a-1)<<endl;
else add(a,b);
}
}