No.1 hdoj-1754(单点的更新与区间最大值）
1 #include<cstdio> 2 #include<algorithm> 3 #define lson l,m,root<<1 4 #define rson m+1,r,root<<1|1 5 const int N=200001; 6 using namespace std; 7 int n,m; 8 int seg[N*4]; 9 void pushup (int root) { 10 seg[root]=max(seg[root<<1],seg[root<<1|1]); 11 return ; 12 } 13 void build (int l,int r,int root ) { 14 if (l==r) { 15 scanf("%d",&seg[root]); 16 return ; 17 } 18 int m=(l+r)>>1; 19 build(lson); 20 build(rson); 21 pushup(root); 22 return ; 23 } 24 int Query (int L,int R,int l,int r,int root) { 25 if (r<L||l>R) return -1; 26 if (l>=L&&r<=R) return seg[root]; 27 int m=(l+r)>>1; 28 int t1=Query (L,R,lson); 29 int t2=Query (L,R,rson); 30 return max(t1,t2); 31 } 32 void update (int p,int x,int l,int r,int root) { 33 if (l==r) { 34 seg[root]=x;// 易错点 seg[l]=x; 请注意是对节点的更新 35 return ; 36 } 37 int m=(l+r)>>1; 38 if (p<=m) update(p,x,lson); 39 else update(p,x,rson); 40 pushup(root); 41 return; 42 } 43 int main() 44 { 45 while (scanf("%d %d",&n,&m)==2) { 46 build(1,n,1); 47 char s[10]; 48 int a,b; 49 for (int i=1;i<=m;i++) { 50 scanf("%s %d %d",s,&a,&b); 51 if (s[0]=='Q') printf("%d ",Query(a,b,1,n,1)); 52 if (s[0]=='U') update(a,b,1,n,1); 53 } 54 } 55 return 0; 56 }
No.2-hdoj 1166(单点更新区间求和）都是套路 感觉这样的题还是树状数组做着简单
1 #include<cstdio> 2 #include<algorithm> 3 #define lson l,m,root<<1 4 #define rson m+1,r,root<<1|1 5 const int N=50001; 6 using namespace std; 7 int n,m; 8 int seg[N*4]; 9 void pushup (int root) {// 相比于上一个程序只是变了一小下 10 seg[root]=seg[root<<1]+seg[root<<1|1]; 11 return ; 12 } 13 void build (int l,int r,int root ) { 14 if (l==r) { 15 scanf("%d",&seg[root]); 16 return ; 17 } 18 int m=(l+r)>>1; 19 build(lson); 20 build(rson); 21 pushup(root); 22 return ; 23 } 24 int Query (int L,int R,int l,int r,int root) { 25 if (r<L||l>R) return 0; 26 if (l>=L&&r<=R) return seg[root]; 27 int m=(l+r)>>1; 28 int t1=Query (L,R,lson); 29 int t2=Query (L,R,rson); 30 return t1+t2; 31 } 32 void update (int p,int x,int l,int r,int root) { 33 if (l==r) { 34 seg[root]+=x; 35 return ; 36 } 37 int m=(l+r)>>1; 38 if (p<=m) update(p,x,lson); 39 else update(p,x,rson); 40 pushup(root); 41 return; 42 } 43 int main() 44 { 45 int T; int num=1; 46 scanf ("%d",&T); 47 while (T--) { 48 printf ("Case %d: ",num++); 49 scanf ("%d",&n); 50 build(1,n,1); 51 char s[10]; 52 int a,b; 53 while (1) { 54 scanf(" %s",s); 55 if (s[0]=='E') break; 56 scanf ("%d %d",&a,&b); 57 if (s[0]=='Q') printf("%d ",Query(a,b,1,n,1)); 58 else if (s[0]=='A') update(a,b,1,n,1); 59 else update(a,-b,1,n,1); 60 } 61 } 62 return 0; 63 }
No.3-hdoj 1698 (线段树的核心-懒惰标记区间更新）
1 #include<cstdio> 2 #include<algorithm> 3 #include <iostream> 4 #include <cstring> 5 #define lson l,mid,root<<1 6 #define rson mid+1,r,root<<1|1 7 const int N=1e5+7; 8 using namespace std; 9 int n,m; 10 int seg[N*4]; 11 int mark[N*4]; 12 inline void pushup (int root) { 13 seg[root]=seg[root<<1]+seg[root<<1|1]; 14 } 15 inline void pushdown (int root,int l,int r) {//直接更新区间而不是整个区间的点 如果要对区间的子区间进行操作 先进行pushdown 16 mark[root<<1]=mark[root<<1|1]=mark[root]; 17 int mid=(l+r)/2; 18 seg[root<<1]=(mid-l+1)*mark[root]; 19 seg[root<<1|1]=(r-mid)*mark[root]; 20 mark[root]=0;// 不要忘了 21 } 22 void build (int l,int r,int root ) { 23 if (l==r) { 24 seg[root]=1; 25 return ; 26 } 27 int mid=(l+r)>>1; 28 build(lson); 29 build(rson); 30 pushup(root); 31 return ; 32 } 33 void update (int L,int R,int x, int l,int r,int root) { 34 if (l>R||r<L) return ; 35 if (l>=L&&r<=R) { 36 mark[root]=x; 37 seg[root]=(r-l+1)*x; 38 return ; 39 } 40 int mid=(l+r)/2; 41 if (mark[root]) pushdown (root,l,r); 42 update (L,R,x,lson); 43 update (L,R,x,rson); 44 pushup (root); 45 return ; 46 } 47 int main() 48 { 49 int T; int num=1; 50 scanf ("%d",&T); 51 while (T--) { 52 scanf ("%d %d",&n,&m); 53 memset (mark,0,sizeof(mark));//初始化。又忘了 54 build(1,n,1); 55 for (int i=1;i<=m;i++) { 56 int x,y,k; 57 scanf ("%d %d %d",&x,&y,&k); 58 update (x,y,k,1,n,1); 59 } 60 printf("Case %d: The total value of the hook is ",num++); 61 printf ("%d. ",seg[1]); 62 } 63 return 0; 64 }
No.4 线段树实际运用--贴海报——hdoj2795（区间最值）
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define lson l,m,root<<1 5 #define rson m+1,r,root<<1|1 6 using namespace std; 7 const int N=200001; 8 int segtree[N*4]; 9 int h,w,n; 10 void build (int l,int r,int root) { 11 segtree[root]=w; 12 if (l==r) return ; 13 int m=(l+r)>>1; 14 build(lson); 15 build (rson); 16 return ; 17 } 18 int Query (int x,int l,int r,int root) { 19 if (l==r) { 20 segtree[root]-=x; 21 return l; 22 } 23 int ans; 24 int m=(l+r)>>1; 25 if (x<=segtree[root<<1]) ans=Query(x,lson); 26 else ans=Query(x,rson); 27 segtree[root]=max(segtree[root<<1],segtree[root<<1|1]); 28 return ans; 29 } 30 int main() 31 { 32 while (scanf("%d %d %d",&h,&w,&n)==3) { 33 if (h>n) h=n; 34 build (1,h,1); 35 for (int i=1;i<=n;i++) { 36 int x; 37 scanf("%d",&x); 38 if (x>segtree[1]) printf("-1 "); 39 else printf("%d ",Query(x,1,h,1)); 40 } 41 } 42 return 0; 43 }