遞歸代碼：

#include <string> #include <cstring> #include <iostream> #include <stdio.h> using namespace std; const int inf=1e5+7; //最多的數量。 int sum[inf<<2],add[inf<<2]; //其中的值都為零。 int arr[inf],n;void PushUp(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];} //應該是按照順序進行的吧。 void BuiltTree(int l,int r,int rt) //建樹。 {if(l==r) //說明是到達了葉子結點。{sum[rt]=arr[l];return ;}int m=(l+r)>>1;BuiltTree(l,m,rt<<1);BuiltTree(m+1,r,rt<<1|1);PushUp(rt); } //點修改，A[L]+=C; void UpDate(int l,int r,int L,int C,int rt) {if(l==r){sum[rt]+=C; //這里。return ;}int m=(l+r)>>1;if(L<=m)UpDate(l,m,L,C,rt<<1);elseUpDate(m+1,r,L,C,rt<<1|1);PushUp(rt); } //下推標志。 void PushDown(int l,int r,int rt) {if(add[rt]){int m=(l+r)>>1;sum[rt<<1]+=(m-l+1)*add[rt];sum[rt<<1|1]+=(r-m)*add[rt];add[rt<<1]+=add[rt];add[rt<<1|1]+=add[rt];add[rt]=0;} } //區間修改，A[L到R]+=C; void UpDate1(int l,int r,int rt,int L,int R,int C) //有可能有多次修改。所以每到一個結點都要下推標志。 {if(l>=L&&r<=R){sum[rt]+=(r-l+1)*C;add[rt]+=C;return ;}PushDown(l,r,rt);int m=(l+r)>>1;if(L<=m)UpDate1(l,m,rt<<1,L,R,C);if(R>m)UpDate1(m+1,r,rt<<1|1,L,R,C);PushUp(rt); } //區間查詢。 求arr[L到R]的和。 int DateQuery(int l,int r,int rt,int L,int R) {if(l>=L&&r<=R){return sum[rt];}PushDown(l,r,rt);int m=(l+r)>>1;int ans=0; //如果數據過大的話用long long.if(L<=m)ans+=DateQuery(l,m,rt<<1,L,R);if(R>m)ans+=DateQuery(m+1,r,rt<<1|1,L,R);return ans; } void display() {for(int i=1;i<=4*n;i++)printf("%d ",sum[i]);printf("\n"); }int main() {cout<<"請輸入數組的個數"<<endl;cin>>n;cout<<"請輸入數據"<<endl;for(int i=1;i<=n;i++){scanf("%d",&arr[i]);}BuiltTree(1,n,1);display();int flag=0;cout<<"是否進行點修改？是，1；否，0"<<endl;cin>>flag;if(flag==1){int C,L;cout<<"請輸入要修改的點和數據"<<endl;cin>>L>>C;UpDate(1,n,L,C,1);display();}cout<<"是否進行區間修改，是，1：否，0"<<endl;cin>>flag;if(flag==1){int L,R,C;cout<<"請輸入左右區間和數據"<<endl;cin>>L>>R>>C;UpDate1(1,n,1,L,R,C);display();}cout<<"是否進行區間求和，是，1：否，0"<<endl;cin>>flag;if(flag==1){int L,R;cout<<"請輸入左右端點"<<endl;cin>>L>>R;cout<<"結果是"<<endl;cout<<DateQuery(1,n,1,L,R)<<endl;}return 0; }

?

非遞歸代碼：

#include <iostream> //線段樹。 #include <cstring> #include <string> using namespace std; const int inf=100007; int Sum[inf<<2]; //初始的應該是零吧。 int Add[inf<<2]; int A[inf]; int n,N; void Build(int n) //首先進行創建。 { N=1;while(N<n+2)N<<=1; //首先找出N來。 for(int i=1;i<=n;i++) Sum[i+N]=A[i]; //之后看看兩邊的還要管嗎。 for(int i=N-1;i>0;i--) { Sum[i]=Sum[i<<1]+Sum[i<<1|1]; Add[i]=0; //在這里進行修改嗎。 } } void Update(int L,int C) //之后是進行點修改。sum[l]+=C; { for(int s=L+N;s;s>>=1) { Sum[s]+=C; } } int Query(int L,int R) //點修改下的區間查詢。sum[L R]的和。 { int ans=0; for(int s=L+N-1,t=R+N+1;s^t^1;s>>=1,t>>=1) { if(~s&1)ans+=Sum[s^1]; if(t&1)ans+=Sum[t^1]; } return ans; } void Update1(int L,int R,int C) //區間修改Sum[L R]+=C; { int s,t,Ln=0,Rn=0,x=1; for(s=L+N-1,t=R+N+1;s^t^1;s>>=1,t>>=1,x<<=1 ) { Sum[s]+=Ln*C; Sum[t]+=Ln*C; //這里。 if(~s&1)Add[s^1]+=C,Sum[s^1]+=C*x,Ln+=x; if(t&1) Add[t^1]+=C,Sum[t^1]+=C*x,Rn+=x; } for( ;s;s>>=1,t>>=1) //鏈接還是巧妙的啊。 { Sum[s]+=C*Ln; Sum[t]+=C*Rn; } } int Query1(int L,int R) //區間修改上的區間查詢。sum【L，R】的和。 { int s,t,Ln=0,Rn=0,x=1; int ans=0; for(s=L+N-1,t=R+N+1;s^t^1;s>>=1,t>>=1,x<<=1) { if(Add[s])ans+=Add[s]*Ln; if(Add[t])ans+=Add[t]*Rn; if(~s&1)ans+=Sum[s^1],Ln+=x; if( t&1)ans+=Sum[t^1],Rn+=x; } for( ;s;s>>=1,t>>=1) //其實加不加是無所謂的。 { /*if( Add[s])*/ans+=Add[s]*Ln; //這里為何是不加的呢。 /*if( Add[t])*/ans+=Add[t]*Rn; } return ans; }int main() { cout<<"請輸入數組的個數"<<endl; cin>>n; cout<<"請輸入數組中的值"<<endl; for(int i=1;i<=n;i++) cin>>A[i]; Build(n); //初始化。 for(int i=1;i<=2*N-1;i++) cout<<Sum[i]<<" "; cout<<endl; Update(3,1); for(int i=1;i<=2*N-1;i++) cout<<Sum[i]<<" "; cout<<endl; int ans=Query(2,4); cout<<ans<<endl; Update1(2,4,1); for(int i=1;i<=2*N-1;i++) cout<<Sum[i]<<" "; cout<<endl; int ans1=Query1(1,4); //最后一個。 cout<<ans1<<endl; return 0; }

hdu1166 敵兵布陣

http://acm.hdu.edu.cn/showproblem.php?pid=1166

簡單線段樹點修改和區間查詢：

代碼：

#include <string> #include <cstring> #include <iostream> #include <stdio.h> using namespace std; const int inf=1e5+7; //最多的數量。 int sum[inf<<2],add[inf<<2]; //其中的值都為零。 int arr[inf],n;void PushUp(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];} //應該是按照順序進行的吧。 void BuiltTree(int l,int r,int rt) //建樹。 {if(l==r) //說明是到達了葉子結點。{sum[rt]=arr[l];return ;}int m=(l+r)>>1;BuiltTree(l,m,rt<<1);BuiltTree(m+1,r,rt<<1|1);PushUp(rt); } //點修改，A[L]+=C; void UpDate(int l,int r,int L,int C,int rt) {if(l==r){sum[rt]+=C; //這里。return ;}int m=(l+r)>>1;if(L<=m)UpDate(l,m,L,C,rt<<1);elseUpDate(m+1,r,L,C,rt<<1|1);PushUp(rt); } //下推標志。 void PushDown(int l,int r,int rt) {if(add[rt]){int m=(l+r)>>1;sum[rt<<1]+=(m-l+1)*add[rt];sum[rt<<1|1]+=(r-m)*add[rt];add[rt<<1]+=add[rt];add[rt<<1|1]+=add[rt];add[rt]=0;} } //區間修改，A[L到R]+=C; void UpDate1(int l,int r,int rt,int L,int R,int C) //有可能有多次修改。所以每到一個結點都要下推標志。 {if(l>=L&&r<=R){sum[rt]+=(r-l+1)*C;add[rt]+=C;return ;}PushDown(l,r,rt);int m=(l+r)>>1;if(L<=m)UpDate1(l,m,rt<<1,L,R,C);if(R>m)UpDate1(m+1,r,rt<<1|1,L,R,C);PushUp(rt); } //區間查詢。 求arr[L到R]的和。 int DateQuery(int l,int r,int rt,int L,int R) {if(l>=L&&r<=R){return sum[rt];}PushDown(l,r,rt);int m=(l+r)>>1;int ans=0; //如果數據過大的話用long long.if(L<=m)ans+=DateQuery(l,m,rt<<1,L,R);if(R>m)ans+=DateQuery(m+1,r,rt<<1|1,L,R);return ans; } void display() {for(int i=1;i<=4*n;i++)printf("%d ",sum[i]);printf("\n"); }int main() {int t;scanf("%d",&t);int abc=1;while(t--){printf("Case %d:\n",abc++);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&arr[i]);BuiltTree(1,n,1);string str;while(1){cin>>str;if(str=="End")break;int a,b;scanf("%d %d",&a,&b);if(str=="Query"){printf("%d\n",DateQuery(1,n,1,a,b));} else if(str=="Add")UpDate(1,n,a,b,1);else{b=-1*b;UpDate(1,n,a,b,1);} }}return 0; }

?

?

總結

以上是生活随笔為你收集整理的线段树递归和非递归实现+hdu1166 敌兵布阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。