树状数组
[Dr.Lib]Note:Algorithms – 树状数组
树状数组是个简单高效的数据结构，实质上是省掉一半空间后的线段树加上中序遍历{Via ZKW《统计的力量》}
一般情况下，他可以做到单点更新，区间求和。
http://wikioi.com/problem/1080/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<iostream> #include<cstdlib> #include<cstdio> #include <cstring> using namespace std; int c[100020]={0},n=0,tmp=0,i=1,p=0,q=0,m=0; inline int lowbit(int x){ return x&(-x); } int sum(int x){ int sum=0; while(x>0){ sum+=c[x]; x-=lowbit(x); } return sum; } void upd(int x,int v){ while(x<=n){ c[x]+=v; x+=lowbit(x); } } int main() { cin>>n; while(i<=n){cin>>tmp;upd(i,tmp);++i;} cin>>m; while(m--){ cin>>tmp; if(tmp==2){cin>>p>>q;cout<<(sum(q)-sum(p-1))<<endl;} else{cin>>p>>q;upd(p,q);} } return 0; } |
小小的差分一下，就可以做到区间更新单点值
http://wikioi.com/problem/1081/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<iostream> #include<cstdlib> #include<cstdio> #include <cstring> using namespace std; int c[100020]={0},n=0,tmp=0,i=1,p=0,q=0,r=0,m=0; inline int lowbit(int x){ return x&(-x); } int sum(int x){ int sum=0; while(x>0){ sum+=c[x]; x-=lowbit(x); } return sum; } void upd(int x,int v){ while(x<=n){ c[x]+=v; x+=lowbit(x); } } int main() { cin>>n; int pre=0; while(i<=n){cin>>tmp;upd(i,tmp-pre);++i;pre=tmp;} cin>>m; while(m--){ cin>>tmp; if(tmp==2){cin>>p;cout<<sum(p)<<endl;} else{cin>>p>>q>>r;upd(p,r);upd(q+1,-r);} } return 0; |
问题是区间更新区间和呢？
只能上线段树了吗？
NO！
http://wikioi.com/problem/1082/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<algorithm> #include<cstring> #include <cstdio> #include<cstdlib> #include<vector> using namespace std; #define MAXN 200020 int n,q; int l,r,k,x; long long c[MAXN],s[MAXN],t[MAXN]; inline int lowbit(int x){return x&(-x);} long long ssum(int x){ long long ans=0; while(x>0){ ans+=s[x]; x-=lowbit(x); } return ans; } long long tsum(int x){ long long ans=0; while(x>0){ ans+=t[x]; x-=lowbit(x); } return ans; } void sadd(int xx,long long val){while(xx<=n)s[xx]+=val,xx+=lowbit(xx);} void tadd(int xx,long long val){while(xx<=n)t[xx]+=val,xx+=lowbit(xx);} int main(){ memset(c,0,sizeof(c)); memset(s,0,sizeof(s)); memset(t,0,sizeof(t)); scanf("%d",&n); for (int i=a;i<=b;i++) scanf("%d",&x),c[i]=c[i-1]+x; scanf("%d",&q); while(q--){ scanf("%d%d%d",&x,&l,&r); if(x==1){ scanf("%d",&k); sadd(l,k);sadd(r+1,-k); tadd(l,(l-1)*k);tadd(r+1,-r*k); }else{ printf("%lld\n",((c[r]-c[l-1])+(1-l)*ssum(l)+r*ssum(r)-(tsum(r)-tsum(l)))); } } return 0; } |
朴素线段树
*计算几何在长期的发展中，
诞生了许多实用的数据结构。*区间查询，穿刺查询都是计算几何解决的问题*作为特例中的特例，线段树解决的问题是：*一维空间上的几何统计
Via 《统计的力量》
线段树（Segment Tree）是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶子节点[a,b]，它的左子树表示的区间为[a,(a+b)/2]，右子树表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树。叶节点数目为N，即整个线段区间的长度。
http://wikioi.com/problem/1191
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int n,m; int ls[800100]; int rs[800100]; int ts[800100]; void build(int l,int r,int p) { ls[p]=l; rs[p]=r; ts[p]=1; if(l<r) { build(l,((l+r)>>1),(p<<1)); build(((l+r)>>1)+1,r,(p<<1)+1); } if(l!=r) ts[p]=ts[p<<1]+ts[(p<<1)+1]; } void inst(int l,int r,int p){if(ts[p]){ if(l<=ls[p]&&rs[p]<=r){ts[p]=0;return;} if(ls[p]==rs[p])return; if(!(l>rs[p<<1]||r<ls[p<<1])){inst(l,r,(p<<1));} if(!(l>rs[(p<<1)+1]||r<ls[(p<<1)+1])){inst(l,r,(p<<1)+1);} ts[p]=ts[p<<1]+ts[(p<<1)+1]; }} int main() { int lp,rp; scanf("%d%d",&n,&m); build(1,n,1); for(int i=1;i<=m;i++) { scanf("%d%d",&lp,&rp); inst(lp,rp,1); printf("%d\n",ts[1]); } return 0; } |
ZKW线段树
参见《统计的力量》
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define N 50005 bool U[4*N]; int T[4*N],M; void update(int n,int V){ n+=M; T[n]=V;U[n]=1; for(n>>=1;n;n>>=1){ T[n]=T[n<<1]+T[(n<<1)+1];U[n]=1;} } int query(int ss,int tt){ int ans=0; for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;ss>>=1,tt>>=1) { if (~ss&1) ans=+T[ss^1]; if ( tt&1) ans=+T[tt^1]; } return ans; } int n,s,t,k; int main (){ cin>>n; for(M=1;M<=n+1;M*=2); while(n--){ cin>>k>>s>>t; if(k) update(s,t); else cout<<query(s,t)<<endl; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define N 50005 bool U[4*N]; int T[4*N],S[4*N],M; int count(int n){ int h=1; while((n<<=1)<(M*2))h<<=1; return h; } int query(int ss,int tt){//查询[ss,tt] int ans=0,tlc=0,trc=0; for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;) { if (~ss&1){ans+=T[ss^1];tlc+=count(ss^1);}//左端点是左孩子 if ( tt&1){ans+=T[tt^1];trc+=count(tt^1);}//右端点是右孩子 ss>>=1;tt>>=1; ans+=tlc*S[ss]+trc*S[tt]; } for (ss >>= 1;ss > 0; ss >>= 1) { ans += S[ss]*(tlc+trc); } return ans; } void inc(int ss,int tt,int vv){//[ss,tt]全部加上一个数 int tlc=0,trc=0; for (ss=ss+M-1,tt=tt+M+1;ss^tt^1;) { if (~ss&1){S[ss^1]+=vv;T[ss^1]+=vv*count(ss^1);tlc+=count(ss^1);}//左端点是左孩子 if ( tt&1){S[tt^1]+=vv;T[tt^1]+=vv*count(tt^1);trc+=count(tt^1);}//右端点是右孩子 ss>>=1;tt>>=1; T[ss]+=tlc*vv;T[tt]+=trc*vv; } for (ss >>= 1;ss > 0; ss >>= 1) { T[ss] += vv*(tlc+trc); } } void update(int n,int V){//置[n,n]为V [problem spec int per=query(n,n); inc(n,n,-per); inc(n,n,V); } int n,s,t,k; int main (){ cin>>n; for(M=1;M<=n+1;M*=2); while(1){ cin>>k>>s>>t; if(k==2) {cin>>k;inc(s,t,k);} else if(k==1) update(s,t); else if(k==0) cout<<query(s,t)<<endl; } return 0; } |
[Dr.Lib]Note:Data Structures – 数据结构那些事 by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.