开始集训了 =-=
估计也就1 2星期的热度吧 自己 好好提高就是了 ~
今天 起晚了....
来做的时候 前面3题很水 看到第4个 很明显 线段树 不会手写了..
----碎碎念
线段树 题目类型 貌似 一般分成
单点更新 区间查询
区间更新 单点查询
区间更新 区间查询
线段树的种类又分成 -- 点树 && （忘记了)...
反正2者的区别就是叶结点的不同与建树的时候 对于右子树的不同写法
一个是[1,1] 一个是[1,2]对于叶结点
一个是create(root<<1|1 , mid+1 , r) 一个是create(root<<1|1 , mid , r)
先放出这2题：一题----单点更新 区间询问 另一题----区间更新 询问呢是很特别的直接O（1）可以进行输出
第一种情况是最简单----- 单点更新 区间询问
建树的过程 是第一步 也是最关键的 反正要是明白了建树的过程 而且清楚了root与下标之间的关系 就理解起来下面的更好了
贴下我画的图----能看懂就好 不要太计较 =-=
紫色的是root结点编号 黑色的是该root所表达的区间
更新的退出条件呢就是---index(更新点的坐标) 与 root的[ tree[root].l , tree[root].r ]分别相等就可以了
要是不相等嘛 你就判断下 index 与这个tree[root].mid的大小关系吧
要是比它小或者相等嘛 那就update或者讲查询这个root的左子树----- 至于原因 一定要看懂 建树的过程 OK
要是比它大嘛 那就update或者讲查询这个root的右子树----至于原因 同上...
查询的退出条件呢就是--查询的区间[ l , r ]与root的[ tree[root].l , tree[root].r ]分别相等就可以了
这里如果不完全相等嘛 就是会比上面更新的时候复杂点 下面tree[root].mid我写成mid 方便点
1. 如果 L > mid 那么你可以参照上面的建树图 自己给个数据 去对比下 你就会发现 应该去查询它的 右子树
2.如果 mid >=r 同理--------------- 然后去查询它的 左子结点 这都与它的建树密切相关
3.第三种情况查询区间既包含 左子树部分 又 包含 右子树部分 那么就同时查询嘛 =-=
这讲的肯定不好 只是给我自己看看的 对于线段树 我也没什么好点的博客推荐....
当你线段树基础的明白后 可以去学下它的变形 树状数组 可能变形这个词语用的不好
树状数组在它适用的范围内比线段树更加高效 而且写起来简单多了啊
下面 贴下上面2题的代码：
关于区间更新 单点查询的内容 我会在下一篇或者下下篇里讲 先欠着
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 5 struct xianduan 6 { 7 int l; 8 int r; 9 int mark; 10 }stu[600000]; 11 12 void create(int root,int l,int r) 13 { 14 int mid=(l+r)/2; 15 stu[root].l=l; 16 stu[root].r=r; 17 if(l==r) 18 { 19 scanf("%d",&stu[root].mark); 20 return; 21 } 22 create(root*2,l,mid); 23 create(root*2+1,mid+1,r); 24 stu[root].mark=max(stu[root*2].mark,stu[root*2+1].mark); 25 26 } 27 28 int query(int root,int l,int r) 29 { 30 int mid=(stu[root].l+stu[root].r)/2; 31 if(stu[root].r==r&&stu[root].l==l) 32 { 33 return stu[root].mark; 34 } 35 if(l>mid) 36 { 37 return query(root*2+1,l,r); 38 } 39 else if(mid>=r) 40 { 41 return query(root*2,l,r); 42 } 43 else 44 { 45 return max( query(root*2,l,mid), query(root*2+1,mid+1,r) ); 46 } 47 } 48 49 void update(int root,int index,int num) 50 { 51 int mid=(stu[root].l+stu[root].r)/2; 52 stu[root].mark=num; 53 if(stu[root].l==index&&stu[root].r==index) 54 { 55 return; 56 } 57 if(index>mid) 58 { 59 return update(root*2+1,index,num); 60 } 61 else 62 { 63 return update(root*2,index,num); 64 } 65 } 66 67 int main() 68 { 69 int a,b,n,m; 70 char ch; 71 while(~scanf("%d %d",&n,&m)) 72 { 73 create(1,1,n); 74 getchar(); 75 while(m--) 76 { 77 scanf("%c %d %d",&ch,&a,&b); 78 if(ch=='Q') 79 { 80 printf("%d ",query(1,a,b)); 81 } 82 else 83 { 84 update(1,a,b); 85 } 86 getchar(); 87 } 88 } 89 }
1 // 线段树的区间更新 2 3 #include <iostream> 4 using namespace std; 5 6 const int size = 52000; 7 struct data 8 { 9 int l; 10 int r; 11 int sum; 12 bool flag; 13 }tree[size*2+100]; 14 15 void create( int root , int l , int r ) 16 { 17 int mid = (l+r)>>1; 18 tree[root].l = l; 19 tree[root].r = r; 20 tree[root].flag = false; 21 if( l == r ) 22 { 23 tree[root].sum = 1; 24 return; 25 } 26 create( root<<1 , l , mid ); 27 create( root<<1|1 , mid+1 , r ); 28 tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum; 29 } 30 31 void update( int root , int l , int r ) 32 { 33 int mid = ( tree[root].l + tree[root].r )>>1; 34 if( tree[root].flag ) 35 return; 36 if( tree[root].l>=l && tree[root].r<=r ) //更新的区间(l,r)里面包括了root.l与root.r 37 { 38 tree[root].flag = true; 39 tree[root].sum = 0; 40 return; 41 } 42 if( l<=mid ) 43 { 44 update( root<<1 , l , r ); // update( root<<1 , l , mid ); 45 } 46 if( r>mid ) 47 { 48 update( root<<1|1 , l , r ); // update( root<<1|1 , mid+1 , r ); 49 } 50 tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum; 51 } 52 53 int main() 54 { 55 int n , query; 56 int l , r; 57 while( ~scanf("%d",&n) ) 58 { 59 create( 1,1,n ); 60 scanf( "%d",&query ); 61 while( query-- ) 62 { 63 scanf( "%d %d",&l,&r ); 64 update( 1 , l , r ); 65 printf( "%d ",tree[1].sum ); 66 } 67 } 68 return 0; 69 }
PS: 对于线段树 你可以采用很多的define来使它变得更加简洁 美观 就是求它的左右子结点啊什么的时候
today:
我遇见很多像你的人 但再也没再遇见过你
我想和你柔软每一段僵硬的时光
那一刻 春水初生 春林初盛 春风十里 不如你