MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 算法导论学习-线段树(二)

算法导论学习-线段树(二)

www.MyException.Cn  网友分享于:2015-02-08  浏览:0次
算法导论学习-线段树(2)

线段树(1)http://www.cnblogs.com/fu11211129/p/4230000.html

1. 线段树应用之动态点插与统计:

--------------------------------

线段树(1)中讲的应用是区段的插值与统计,我们在线段树结构体中接入cover之一域,cover等于0表示该节点所代表的区域并没有被完全覆盖,cover大于等于1表示该节点所代表区域已经被完全覆盖,用线段树(1)博客里面的图来说明一下:

                  

如上图所示,我们最后统计的时候是找出cover不为零的节点,(再上图对应的是节点[3,4]. [5,6], [2], [4], [5], [7].),但是注意到[3,4]和[4] 还有[5,6]和[5]不能从重复统计,所以最后统计的长度是[2]+[3,4]+[5,6]+[7]=6.所以四根木条在墙上的总投影长是6. 

现在我们可以来归纳一下区段插值的几个重要部分:首先是插入动作,比如插入[L, R]线段,插入动作需要递归的从根节点开始插入,而递归的出口就是找到能够和[L, R]完全匹配的线段树节点,即找到a[i].left==L AND a[i].right==R,并且同时将a[i].cover值加1.,递归终止。然后是删除动作,假设删除[L, R],同样的也是要从根节点开始删除,也是要递归的找到与[L, R]完全匹配的线段树节点a[i],并且将a[i].cover值减去1.最后是统计,仍然是从根节点开始递归的统计,递归的出口要么是找到的节点a[i]满足a[i].cover>=0,则返回该节点代表的区段长度。要么是找到叶子节点(a[i].left==a[i].right),如果叶子节点的cover不为0,则返回1,否则返回零。

以上是对区段插入的回顾,下面开始介绍动态点插与统计。所谓动态点插(其实是我自己DIY的,所以我就用图表示一下吧,大家理解就好)

如上图所示,1-8表示相互连接的8个槽,然后在这些草内的任意位置放置任意数量个小球,然后让你求出任意区段内[L, R]的小球数量。比如[2,3]区段内的小球数量是2,[1,6]区段内的小球数量是6。要解决这个问题,可以优良中办法,一种方法不用说也知道,暴力嘛,开一个数组A,然后更新数组的值。。这种做法当“槽”的范围过大时是效率很低的。所以这时候线段树再次派上用场了。我们还是用cover域来表示某个节点缩地阿彪范围的小球数量。比如根节点代表1-8槽的小球数量。

###第一步,建立线段树(http://www.cnblogs.com/fu11211129/p/4230000.html 里面有介绍,这里直接跳过)

###第二步,线段树插入(点插)

1 void updatePoint(int pos,int step){
2     a[step].num++;
3     if(a[step].left==a[step].right&&a[step].left==pos) return;//leaf node
4     int mid=(a[step].left+a[step].right)/2;
5     if(pos<=mid) updatePoint(pos,step*2);
6     else updatePoint(pos,step*2+1);
7 }

我们可以看到,线段树点插动作是“一路插值的”,这也不难理解,比如我在第3个槽内放置一个球,那么显然的,节点[3].num=1,但同时的,节点[3,4],[1,2,3,4],[1,2,3,4,5,6,7,8]的num值也是为1.所以线段树点插可以理解记忆为:一路递归向下插值。

###第三步,线段树统计

 1 int query(int L,int R,int step){
 2     if(L==a[step].left&&R==a[step].right){
 3         return a[step].num;
 4     }
 5     else{
 6         int mid=(a[step].left+a[step].right)/2,ans=0;
 7         if(R<=mid) ans+=query(L,R,step*2);
 8         else if(L>=mid+1) ans+=query(L,R,step*2+1);
 9         else{
10             ans+=query(L,mid,step*2)+query(mid+1,R,step*2+1);
11         }
12         return ans;
13     }
14 }

可以看到,线段树点插结果统计是按照区段来查询的,所以递归查询的出口也就是找到与之匹配的节点,然后返回相应的cover值,对应代码2-4行。如果与当前节点不匹配,则递归的“往下”查[6-8],如果带查询区段在左右子树都有子结果,则返回两个子结果之和。

2. 线段树应用之区间最大最小值问题:

-----------------------------------

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int max_size=100;
 6 const int inf=1<<30;
 7 struct segmentTree{
 8     int lc,rc,mi,mx;
 9 }a[max_size*3];
10 void buildTree(int L,int R,int rt){
11     a[rt].lc=L;
12     a[rt].rc=R;
13     a[rt].mi=inf;
14     a[rt].mx=-inf;
15     if(L==R) return;
16     int mid=(a[rt].lc+a[rt].rc)/2;
17     buildTree(L,mid,rt*2);
18     buildTree(mid+1,R,rt*2+1);
19 }
20 void insert(int pos,int v,int rt){
21     if(pos==a[rt].lc&&a[rt].lc==a[rt].rc){
22         a[rt].mi=v;
23         a[rt].mx=v;
24         return;
25     } 
26     int mid=(a[rt].lc+a[rt].rc)/2;
27     if(pos<=mid) insert(pos,v,rt*2);
28     else insert(pos,v,rt*2+1);
29     a[rt].mi=min(a[rt*2].mi,a[rt*2+1].mi);
30     a[rt].mx=max(a[rt*2].mx,a[rt*2+1].mx);
31 }
32 int query_min(int L,int R,int rt){
33     if(L==a[rt].lc&&R==a[rt].rc) return a[rt].mi;
34     if(a[rt].lc<a[rt].rc){
35         int mid=(a[rt].lc+a[rt].rc)/2,ret;
36         if(R<=mid) ret=query_min(L,R,rt*2);
37         else if(L>=mid+1) ret=query_min(L,R,rt*2+1);
38         else ret=min(query_min(L,mid,rt*2),query_min(mid+1,R,rt*2+1));
39         return ret;
40     }
41 }
42 int main(){
43     int n,m,q,p,v;
44     while(scanf("%d",&n)!=EOF){
45         buildTree(1,n,1);
46         scanf("%d",&m);
47         for(int i=1;i<=m;i++){
48             scanf("%d%d",&p,&v);
49             insert(p,v,1);
50         }
51         scanf("%d",&q);
52         while(q--){
53             int a,b;
54             scanf("%d%d",&a,&b);
55             printf("%d\n",query_min(a,b,1));
56         }
57     }
58 }

 

文章评论

程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
如何成为一名黑客
如何成为一名黑客
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
老程序员的下场
老程序员的下场
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
我是如何打败拖延症的
我是如何打败拖延症的
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
为什么程序员都是夜猫子
为什么程序员都是夜猫子
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员必看的十大电影
程序员必看的十大电影
漫画:程序员的工作
漫画:程序员的工作
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
一个程序员的时间管理
一个程序员的时间管理
总结2014中国互联网十大段子
总结2014中国互联网十大段子
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
那些争议最大的编程观点
那些争议最大的编程观点
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
每天工作4小时的程序员
每天工作4小时的程序员
程序员都该阅读的书
程序员都该阅读的书
代码女神横空出世
代码女神横空出世
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员应该关注的一些事儿
程序员应该关注的一些事儿
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
编程语言是女人
编程语言是女人
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
 程序员的样子
程序员的样子
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
中美印日四国程序员比较
中美印日四国程序员比较
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
我的丈夫是个程序员
我的丈夫是个程序员
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员和编码员之间的区别
程序员和编码员之间的区别
Java程序员必看电影
Java程序员必看电影
程序员的鄙视链
程序员的鄙视链
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
10个调试和排错的小建议
10个调试和排错的小建议
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
旅行,写作,编程
旅行,写作,编程
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有