首页 > 代码库 > 树状数组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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。