lowbit
数组的第 i 位存储的是以 i 为结尾的长度为lowbit(i) 的一段的和.
int lowBit(x) {
return x & -x;
}
加点
int n, bt[maxn];
void btAdd(int pos, int delta) {
for (; pos <= n; pos += lowBit(p)) {
bt[pos] += delta;
}
}
查询
int btSum(int pos) {
int ans = ;
for (; pos; pos -= lowBit(p)) {
ans += bt[p];
}
return ans;
}
完整代码
略有不同的，dad曾经教给我，树状数组这么写
//线段树练习1
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
using namespace std;
int n,m,t[maxn];
void add(int k,int z)
{
while(k<=n)
{
t[k]+=z;
k+=k&(-k);
}
}
int find(int k)
{
int ans=;
while(k)
{
ans+=t[k];
k-=k&(-k);
}
return ans;
}
int main()
{
int i,j,k,x;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d",&x);
add(i,x);
}
scanf("%d",&m);
for(i=;i<=m;i++)
{
int x,y,z,w;
scanf("%d",&w);
scanf("%d%d",&x,&y);
if(w==)
add(x,y);
else if(w==)
printf("%d\n",find(y)-find(x-));
}
return ;
}
//线段树练习2
#include<iostream>
using namespace std;
int t[],n,m;
void add(int k,int z)
{
while(k<=n)
{
t[k]+=z;
k+=k&(-k);
}
}
int find(int a)
{
int ans=;
while(a)
{
ans+=t[a];
a-=a&(-a);
}
return ans;
}
int main()
{
int s;
cin>>n;
for(int i=;i<=n;i++)
cin>>s,
add(i,s);
cin>>m;
for(int i=;i<=m;i++)
{
int x,y,w,z;
cin>>w;
if(w==)
{
cin>>x;
cout<<find(x)-find(x-)<<endl;
}
if(w==)
{
cin>>x>>y>>z;
for(int j=x;j<=y;j++)
add(j,z);
}
}
}