首页 > 代码库 > 2014 summer 知识点总结1之线段树
2014 summer 知识点总结1之线段树
HDU 1166
【题意】：
n个阵营一字排开，每个初始有a[i]个人。现有两种操作：
Q a b 查询[a,b]之间总人数并输出
A/S a b 在a号位添加/删除b个人
【分析】：最基本的单点更新和区间查询，维护节点信息sum[o]
【代码】：
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 5 using namespace std; 6 7 int numv[50005<<2]; 8 int A[50005]; 9 10 void builtTree(int o,int l,int r){11 if(l==r) {12 numv[o]=A[l];13 return ;14 }15 int m=l+(r-l)/2;16 builtTree(2*o,l,m);17 builtTree(2*o+1,m+1,r);18 numv[o]=numv[2*o]+numv[2*o+1];19 return ;20 }21 void Update(int o,int l,int r,int p,int x){22 if(l==r && l==p){23 A[l]=x;24 numv[o]=x;25 return ;26 }27 int m=l+(r-l)/2;28 if (p<=m) Update(2*o,l,m,p,x);29 if (p>=m+1)Update(2*o+1,m+1,r,p,x);30 numv[o]=numv[2*o]+numv[2*o+1];31 }32 int Query(int ql,int qr,int o,int l,int r){33 if (ql<=l && r<=qr) return numv[o];34 int m=l+(r-l)/2;35 int ans=0;36 if (ql<=m) ans+=Query(ql,qr,2*o,l,m);37 if (m+1<=qr) ans+=Query(ql,qr,2*o+1,m+1,r);38 return ans;39 }40 int t,n;41 int main(){42 scanf("%d",&t);43 for(int cas=1;cas<=t;cas++){44 scanf("%d",&n);45 printf("Case %d:\n",cas);46 for(int i=1;i<=n;i++) scanf("%d",&A[i]);47 builtTree(1,1,n);48 char s[105];49 while(~scanf("%s",s)){50 if (s[0]==‘E‘) {51 break;52 }53 int a,b;54 scanf("%d%d",&a,&b);55 if (s[0]==‘Q‘){56 int ans=Query(a,b,1,1,n);57 printf("%d\n",ans);58 }59 if (s[0]==‘A‘){60 Update(1,1,n,a,A[a]+b);61 }62 if (s[0]==‘S‘){63 Update(1,1,n,a,A[a]-b);64 }65 }66 }67 return 0;68 }
HDU 1754
【题意】:给n个数字。m次操作，每次操作更新一个数字或者查询区间最大值。
【分析】：基本单点更新区间查询，维护节点信息max[o]
【代码】：
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #define Mod 1000000007 5 #define LL long long 6 #define toL 2*o,l,m 7 #define toR 2*o+1,m+1,r 8 using namespace std; 9 10 int maxv[200005<<2];11 int A[200005];12 13 void builtTree(int o,int l,int r){14 if (l==r){15 maxv[o]=A[l];16 return ;17 }18 int m=(l+r)/2;19 builtTree(toL);20 builtTree(toR);21 maxv[o]=max(maxv[2*o],maxv[2*o+1]);22 return ;23 }24 void Updata(int o,int l,int r,int p,int x){25 if (l==r && p==l){26 maxv[o]=x;27 return ;28 }else {29 int m=(r+l)/2;30 if (p<=m) Updata(toL,p,x);31 if (m+1<=p) Updata(toR,p,x);32 maxv[o]=max(maxv[2*o],maxv[2*o+1]);33 return ;34 }35 }36 int Query(int o,int l,int r,int ql,int qr){37 if (ql<=l && r<=qr) return maxv[o];38 int m=(r+l)/2;39 int ans=-1;40 if (ql<=m) ans=max(ans,Query(toL,ql,qr));41 if (m+1<=qr) ans=max(ans,Query(toR,ql,qr));42 return ans;43 }44 int n,q;45 46 int main(){47 while(~scanf("%d%d",&n,&q)){48 for(int i=1;i<=n;i++) scanf("%d",&A[i]);49 builtTree(1,1,n);50 for(int i=1;i<=q;i++){51 int a,b;52 char s[3];53 scanf("%s%d%d",s,&a,&b);54 if (s[0]==‘Q‘){55 printf("%d\n",Query(1,1,n,a,b));56 }57 if (s[0]==‘U‘){58 Updata(1,1,n,a,b);59 }60 }61 }62 return 0;63 }
HDU 1394
【题意】:就是给出一串数，当依次在将第一个数变为最后一个数的过程中，要你求它的最小逆序数。
【分析】:每次维护sumv求区间内有多少个数字，处理出LOW[],UP[]后利用sum每次枚举
for(int i=1;i<=n;i++){ scanf("%d",&A[i]); A[i]++; // cout<<"Q="<<Query(1,1,n,A[i]+1,n)<<endl; if (A[i]+1<=n) sum+=Query(1,1,n,A[i]+1,n); updata(1,1,n,A[i],1);//令A【i】的位置为1，那么sunv就相当于一个求和了 A[i]--;//信息已经保存到树中，A[i]可还原 }【代码】：
1 /*HDU1394搜索写法*/ 2 #include <iostream> 3 #include <string.h> 4 #include <stdio.h> 5 #define LL 2*o,l,m 6 #define LR 2*o+1,m+1,r 7 using namespace std; 8 9 int A[50005];10 int Low[50005],Up[50005];11 int numv[50005<<2];//[1...50005]有多少个数12 13 int Query(int o,int l,int r,int ql,int qr){14 if (ql<=l && r<=qr) return numv[o];15 int m=(r+l)>>1;16 int ans=0;17 if (ql<=m) ans+=Query(LL,ql,qr);18 if (m+1<=qr) ans+=Query(LR,ql,qr);19 return ans;20 }21 void updata(int o,int l,int r,int p,int x){22 // cout<<"l="<<l<<","<<"r="<<r<<endl;23 24 if (l==r && p==l) {25 numv[o]=1;26 return ;27 }28 int m=(r+l)>>1;29 if (p<=m)updata(LL,p,x);30 if (m+1<=p)updata(LR,p,x);31 numv[o]=numv[2*o]+numv[2*o+1];32 return;33 }34 int main(){35 int n;36 while(~scanf("%d",&n)){37 memset(numv,0,sizeof(numv));38 int ans,sum=0;39 for(int i=1;i<=n;i++){40 scanf("%d",&A[i]);41 A[i]++;42 // cout<<"Q="<<Query(1,1,n,A[i]+1,n)<<endl;43 if (A[i]+1<=n) sum+=Query(1,1,n,A[i]+1,n);44 updata(1,1,n,A[i],1);//令A【i】的位置为1，那么sunv就相当于一个求和了45 A[i]--;//信息已经保存到树中，A[i]可还原46 }47 ans=sum;48 for(int i=0;i<n;i++){49 Low[i]=i;50 Up[i]=n-i-1;51 }52 for(int i=1;i<=n-1;i++){53 sum=sum+(Up[A[i]]-Low[A[i]]);54 ans=min(sum,ans);55 }56 printf("%d\n",ans);57 }58 return 0;59 }
【题意】:
【分析】：
【代码】：
【题意】:
【分析】：
【代码】：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。