（本來對于樹狀數(shù)組沒啥感覺的....畢竟?jié)撘庾R的認為只要樹狀數(shù)組的能夠解決的問題我都可以用線段樹解決，但是對于一些玄學(xué)題目可能會被卡掉T 因為在樹狀數(shù)組能適用的題，他在空間和時間都優(yōu)于線段樹，所以學(xué)好樹狀數(shù)組也是很重要的，具體的實現(xiàn)過程百度.....實質(zhì)上只是二進制的運用 熟練運用二進制就能解決相關(guān)問題；

傳送門http://poj.org/problem?id=3067

題意：在日本的東海岸和西海岸修交通線，問這些交通線有多少交叉點;

解法：按照x坐標升序，相同的情況下y升序排序，然后查詢在之前有多少滿足條件的即可

#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #define N 1005 #define ll long long using namespace std; typedef struct node{int x;int y; friend bool operator <(node a,node b){ if(a.x==b.x) return a.y<b.y; else return a.x<b.x; } }node; node a[N*N]; ll d[N]; int get_id(int x){ return x&(-x); } void update(int x){ while(x<=N){ d[x]++;x+=get_id(x); } } ll Sum(int x){ ll ans=0; while(x>0){ ans+=d[x];x-=get_id(x); } return ans; } int main(){ int T;scanf("%d",&T); int n,m,k;int Case=0; while(T--){ scanf("%d%d%d",&n,&m,&k); int aa,bb; memset(d,0,sizeof(d)); for(int i=1;i<=k;i++){ scanf("%d%d",&a[i].x,&a[i].y); } sort(a+1,a+k+1); update(a[1].y); ll sum=0; for(int i=2;i<=k;i++){ sum+=(i-1-Sum(a[i].y)); update(a[i].y); } printf("Test case %d: ",++Case); printf("%lld\n",sum); } return 0; }

?

傳送門?http://poj.org/problem?id=3321

題意：給你一顆蘋果樹，每個節(jié)點初始都有一個蘋果，執(zhí)行一些操作（有蘋果的直接拿掉 沒有的直接補上去一個蘋果），然后查詢這個節(jié)點的子樹上有多少個蘋果;

解法：第一反應(yīng)樹剖+樹狀數(shù)組查詢區(qū)間和（似乎有更簡單的樹狀數(shù)組 并不會2333333）

#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdio> #include <cstring> #define N 100005 using namespace std; int pos;int son[N];int deep[N];int a[N]; int first[N*2];int Next[N*2];int vi[N*2]; void intx(){ pos=0; deep[0]=0; for(int i=1;i<N;i++) first[i]=-1; for(int i=1;i<N;i++) son[i]=-1; } int fa[N];int num[N]; void dfs1(int v,int pre){ fa[v]=pre;num[v]=1;deep[v]=deep[pre]+1; for(int i=first[v];i!=-1;i=Next[i]){ if(vi[i]!=pre){ dfs1(vi[i],v); num[v]+=num[vi[i]]; if(son[v]==-1||num[son[v]]<num[vi[i]]){ son[v]=vi[i]; } } } } int p[N];int tp[N];int fp[N]; void dfs2(int v,int td){ p[v]=++pos;fp[p[v]]=v;tp[v]=td; if(son[v]!=-1) dfs2(son[v],td); for(int i=first[v];i!=-1;i=Next[i]){ if(vi[i]!=fa[v]&&vi[i]!=son[v]) dfs2(vi[i],vi[i]); } } int d[N]; int get_id(int x){ return x&(-x); } int n; void get_d(int n){ for(int i=1;i<=n;i++){ int j=i; while(j<=n){ d[j]+=a[i];j+=get_id(j); } } } void update(int x,int t){ while(x<=n){ d[x]+=t;x+=get_id(x); } } int Sum(int x){ int ans=0; while(x>0){ ans+=d[x];x-=get_id(x); } return ans; } int main(){ while(scanf("%d",&n)==1){ int aa,bb; intx(); for(int i=1;i<=(n-1)*2;i++){ scanf("%d%d",&aa,&bb); Next[i]=first[aa]; first[aa]=i; vi[i]=bb; i++; Next[i]=first[bb]; first[bb]=i; vi[i]=aa; // vec[aa].push_back(bb);vec[bb].push_back(aa); } dfs1(1,0); dfs2(1,1); memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) a[i]=1; memset(d,0,sizeof(d)); get_d(n); int q;scanf("%d",&q);char s[5]; for(int i=1;i<=q;i++){ scanf("%s",s); if(s[0]=='Q'){ scanf("%d",&aa); int t1=p[aa];int t2=p[aa]+num[aa]-1; printf("%d\n",Sum(t2)-Sum(t1-1)); } else if(s[0]=='C'){ scanf("%d",&aa); if(a[aa]==0){ a[aa]=1;update(p[aa],1); } else{ a[aa]=0;update(p[aa],-1); } } } // for(int i=1;i<=n;i++) vec[i].clear(); } return 0; }

?

傳送門http://poj.org/problem?id=2481

題意：求一個區(qū)間是多少個區(qū)間真子區(qū)間（只允許一個端點相同）

解法：按照x升序排序后，x相同時按照y的降序排序;然后查詢即可（可能存在完全相等的兩個區(qū)間;要注意這個下標從0開始）

#include <iostream> #include <algorithm> #include <cstring> #include <map> #include <vector> #include <cstdio> #define N 100005 using namespace std; typedef struct node{ int x;int y;int biao; friend bool operator<(node a,node b){ if(a.x==b.x) return a.y>b.y; return a.x<b.x; } }node; node a[N]; int d[N];int vis[N]; int get_id(int x){ return x&(-x); } void update(int x){ while(x<=N){ d[x]++;x+=get_id(x); } } void Sum(int x,int biao){ int ans=0; while(x>0){ ans+=d[x]; x-=get_id(x); } vis[biao]=ans; } int main(){ int n; while(scanf("%d",&n)==1&&n){ int xx,yy;node t; memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].x,&a[i].y);a[i].x++;a[i].y++;a[i].biao=i; } int u=0; sort(a+1,a+n+1); for(int i=1;i<=n;i++){ if(i==1){ Sum(a[i].y-1,a[i].biao); vis[a[i].biao]=u-vis[a[i].biao]; } else{ if(a[i].x==a[i-1].x&&a[i].y==a[i-1].y) vis[a[i].biao]=vis[a[i-1].biao]; else{ Sum(a[i].y-1,a[i].biao); vis[a[i].biao]=u-vis[a[i].biao]; } } u++; update(a[i].y); } for(int i=1;i<=n;i++){ if(i==1) printf("%d",vis[i]); else printf(" %d",vis[i]); } printf("\n"); } return 0; }

?傳送門http://poj.org/problem?id=2352

題意：給你每個星星的位置，求這個星星的坐標范圍內(nèi)有多少個星星（包括自己）

題解：按照x升序x相同時升序，查找統(tǒng)計即可；

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #define N 32005 #define M 15005 using namespace std; typedef struct node{int x;int y; friend bool operator<(node a,node b){ if(a.x==b.x) return a.y<b.y; return a.x<b.x; } }node; int n; node a[M]; int d[N];int vis[N]; int get_id(int x){ return x&(-x); } void update(int x){ while(x<=N){ d[x]++; x+=get_id(x); } } void Sum(int x){ int ans=0; while(x>0){ ans+=d[x]; x-=get_id(x); } vis[ans]++; } int main(){ while(scanf("%d",&n)==1){ int xx;int yy; for(int i=1;i<=n;i++){ scanf("%d%d",&xx,&yy);a[i].x=xx+1;a[i].y=yy+1; } memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); sort(a+1,a+n+1); for(int i=1;i<=n;i++){ update(a[i].y); Sum(a[i].y); } for(int i=1;i<=n;i++){ printf("%d\n",vis[i]); } } return 0; }

?最后一題：

傳送門http://poj.org/problem?id=1195

題意：給一個正方形，初始都是0，1操作是一個點的修改，2查詢左下角和右上角形成的矩陣的和

題解：一維樹狀數(shù)組拓展為二維樹狀數(shù)組 在x y方向彼此獨立

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #define ll long long using namespace std; ll d[1030][1030]; int get_id(int x){return x&(-x); } void update(int x,int y,int vulue){for(int i=x;i<=1030;i+=get_id(i)){for(int j=y;j<=1030;j+=get_id(j)){d[i][j]+=vulue;}} } int sum(int x,int y){int ans=0;for(int i=x;i>0;i-=get_id(i)){for(int j=y;j>0;j-=get_id(j)){ans+=d[i][j];}}return ans; } int main(){int k;int n;while(scanf("%d %d",&k,&n)==2){if(k!=0) break;memset(d,0,sizeof(d));int t;int aa,bb,cc,x1,y1;while(scanf("%d",&t)==1&&t!=3){if(t==1){scanf("%d%d%d",&aa,&bb,&cc);update(aa+1,bb+1,cc);}else if(t==2){scanf("%d%d%d%d",&aa,&bb,&x1,&y1);aa++;bb++;x1++;y1++;printf("%d\n",sum(x1,y1)-sum(aa-1,y1)-sum(x1,bb-1)+sum(aa-1,bb-1));}}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wang9897/p/7624491.html

總結(jié)

以上是生活随笔為你收集整理的树状数组总结篇的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。