注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

线段树入门1  

2014-03-07 22:44:41|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我是自学新手,今天刷了wikioi5道线段树的简单题:从简单到难的。
1:P1191数轴染色:就是给你1.到N,然后区间A到B染色,求未染色的部分。
初学,看着模板,先建个从1-N的线段树
用个记录类型:
struct node
{
 int a;int b;int cover;
}tree[600001];
void build(int a,int b,int tot)
 {
 int mid=(a+b)/2;
 tree[tot].a=a;tree[tot].b=b;tree[tot].cover=b-a+1;
 if (a==b) return;
 if (b-a+1>=1)
       {
       build(a,mid,tot*2);
       build(mid+1,b,tot*2+1);
       }
 }
后来几道题初始化都要建树的。然后就插入线段XY,如果找到区间A,B被包含在XY内,就把COVER赋值为0;然后递归求左右儿子,那么这个节点的区间长度就是他们的区间和。
2.P1080线段树练习:给你1到N的区间,有时会在第I个区间+上J,有时会询问I,J的和。这题先用前缀和记录好,然后每次插入I,更新这个区间,递归返回这个节点区间的COVER(初始区间便是用前缀和)。询问,答案便是区间的COVER总和。
3.P1081线段树练习2:对于N个数,操作1:对区间A-B数都加I;2:询问第i个数是多少。
直接线段树插入AB,将A-B区间+i。如N=5,A-B=1-4,那么1-3和4-5都加了I。询问时直接把查找过程中的ANS(LAZY值)加上去。输出即可。因为若第I个数包含在1-5中,那么1-5中的所有数都加了的,所以可以。
4.P1082线段树练习3:对于N个数。操作1:对区间A-B数都加I;2:询问第I-J区间的和是多少。
此题难度较大,直接将A-B区间的每个值都加显然会超时,于是我学了一种LAZY算法(懒惰算法),顾名思义,算法就如他所说的,比较懒惰,例如A-B=1-5,那么我们不需要递归左子树、右子树。受3启发,之间存在1-5区间的LAZY中,即再定义一个tree【num】.lazy。每次无论是查找还是插入,搜索到某个节点,如果他刚好是要插入的区间,那么sum直接加进去,lazy也加进去而后return;如果不是,那么进行算法中的DOWN操作,
如果这个节点的lazy值不为0,那么进入DOWN操作,将SUM和LAZY都加到他的左儿子和右儿子的SUM和LAZY中。
简单代码实现如下:
void down(int num,int x,int y) {
int m=y-x+1; tree[num<<1].cover+=(m-m>>1)*u; tree[(num<<1)+1].cover=(m>>1)*u; tree[num<<1].add+=u; tree[(num<<1)+1].add+=u; tree[num].add=0; } void insert(int num,int x,int y) { if (x==tree[num].a&&y==tree[num].b){ tree[num].cover+=u*(tree[num].b-tree[num].a+1); tree[num].add+=u; return; } if (tree[num].add!=0) down(num,tree[num].a,tree[num].b); int mid=(tree[num].a+tree[num].b)>>1; if (mid>=y) insert(num<<1,x,y); else if (mid<x) insert((num<<1)+1,x,y); else { insert(num<<1,x,mid); insert((num<<1)+1,mid+1,y); } tree[num].cover=tree[num<<1].cover+tree[(num<<1)+1].cover; }
5.开关灯:和4基本一样,下面提供的DOWO和上面的代码神似:
void down(int num,int x,int y)
 {
 int m=y-x+1;
 tree[num<<1].cover=(m-(m>>1))-tree[num<<1].cover;
 tree[(num<<1)+1].cover=(m>>1)-tree[(num<<1)+1].cover;
 tree[num<<1].add=1-tree[num<<1].add;
 tree[(num<<1)+1].add=1-tree[(num<<1)+1].add;
 tree[num].add=0;
 }
void insert(int num,int x,int  y)
 {
 if (x==tree[num].a&&y==tree[num].b){
 tree[num].cover=(tree[num].b-tree[num].a+1)-tree[num].cover;
 tree[num].add=1-tree[num].add;
                                return;
                                     }
 if (tree[num].add==1) down(num,tree[num].a,tree[num].b);
 int mid=(tree[num].a+tree[num].b)>>1;
 if (mid>=y)  insert(num<<1,x,y);
    else if (mid<x) insert((num<<1)+1,x,y);
        else {
             insert(num<<1,x,mid);
             insert((num<<1)+1,mid+1,y);
             }
 tree[num].cover=tree[num<<1].cover+tree[(num<<1)+1].cover;
}利用LAZY思想,下传递。注意查找的时候能传递的也要传递
  评论这张
 
阅读(22)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018