首页 > 代码库 > 树状数组laekov

树状数组laekov

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 = 0;    for (; pos; pos -= lowBit(p)) {        ans += bt[p];    }    return ans;}

完整代码

略有不同的,dad曾经教给我,树状数组这么写

//线段树练习1#include<iostream>#include<cstdio>#include<cstring>#define maxn 100010using 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=0;    while(k)    {        ans+=t[k];        k-=k&(-k);    }    return ans;}int main(){    int i,j,k,x;    scanf("%d",&n);    for(i=1;i<=n;i++)    {        scanf("%d",&x);        add(i,x);     }     scanf("%d",&m);    for(i=1;i<=m;i++)    {        int x,y,z,w;        scanf("%d",&w);        scanf("%d%d",&x,&y);        if(w==1)            add(x,y);        else if(w==2)            printf("%d\n",find(y)-find(x-1));    }    return 0;}
//线段树练习2#include<iostream>using namespace std;int t[100010],n,m;void add(int k,int z){    while(k<=n)    {        t[k]+=z;        k+=k&(-k);    }}int find(int a){    int ans=0;    while(a)    {        ans+=t[a];        a-=a&(-a);    }    return ans;}int main(){    int s;    cin>>n;    for(int i=1;i<=n;i++)      cin>>s,      add(i,s);    cin>>m;    for(int i=1;i<=m;i++)    {        int x,y,w,z;        cin>>w;        if(w==2)          {              cin>>x;              cout<<find(x)-find(x-1)<<endl;          }        if(w==1)          {              cin>>x>>y>>z;              for(int j=x;j<=y;j++)                add(j,z);          }    }}

 

树状数组laekov