首页 > 代码库 > NOJ--1434&&1566--线段树
NOJ--1434&&1566--线段树
开始集训了 =-=
估计也就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）可以进行输出
touch me touch me
第一种情况是最简单----- 单点更新 区间询问
建树的过程 是第一步 也是最关键的 反正要是明白了建树的过程 而且清楚了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 else44 {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 else62 {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\n",query(1,a,b));81 }82 else83 {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\n",tree[1].sum );66 }67 } 68 return 0;69 }
PS: 对于线段树 你可以采用很多的define来使它变得更加简洁 美观 就是求它的左右子结点啊什么的时候
today:
我遇见很多像你的人 但再也没再遇见过你
我想和你柔软每一段僵硬的时光
那一刻 春水初生 春林初盛 春风十里 不如你