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

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

线段树入门【转】  

2009-10-12 20:00:44|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

      我在网上看了一下线段树的介绍,找到了一篇讲的很好而且很适合入门的文章。一般对于一个新的知识,我都会做一道题目后再把自己对算法的理解写下来。不过这一次就算了,因为我对线段树已经没有比这篇文章更好更简单的解释了。这篇文章讲了线段树最基本的理念,以后的问题也大多是在这个基础上进行改进而已。这篇文章的原出处我是没搜到,就暂时copy到下面了,不为别的,只是以后回顾的时候找的方便点。如果这篇文章的作者看到了,记得跟我说句并把链接给我,好让我在这加个链接~~


把问题简化一下:

在自然数,且所有的数不大于30000的范围内讨论一个问题:现在已知n条线段,把端点依次输入告诉你,然后有m个询问,每个询问输入一个点,要求这个点在多少条线段上出现过;

最基本的解法当然就是读一个点,就把所有线段比一下,看看在不在线段中;

每次询问都要把n条线段查一次,那么m次询问,就要运算m*n次,复杂度就是O(m*n)

这道题m和n都是30000,那么计算量达到了10^9;而计算机1秒的计算量大约是10^8的数量级,所以这种方法无论怎么优化都是超时

-----

因为n条线段是固定的,所以某种程度上说每次都把n条线段查一遍有大量的重复和浪费;

线段树就是可以解决这类问题的数据结构

举例说明:已知线段[2,5] [4,6] [0,7];求点2,4,7分别出现了多少次

在[0,7]区间上建立一棵满二叉树:(为了和已知线段区别,用【】表示线段树中的线段)

                                              【0,7】
                               /                                          \
                    【0,3】                                       【4,7】
                  /               \                               /                \
       【0,1】              【2,3】                【4,5】               【6,7】
        /      \                 /      \                  /      \                  /      \
【0,0】  【1,1】    【2,2】 【3,3】   【4,4】 【5,5】     【6,6】 【7,7】

每个节点用结构体:

struct line
{
      int left,right;  //左端点、右端点
      int n;   //记录这条线段出现了多少次,默认为0
}a[16];

和堆类似,满二叉树的性质决定a[i]的左儿子是a[2*i]、右儿子是a[2*i+1];

然后对于已知的线段依次进行插入操作:

从树根开始调用递归函数insert

void insert(int s,int t,int step)  //要插入的线段的左端点和右端点、以及当前线段树中的某条线段
{
      if (s==a[step].left && t==a[step].right)
      {
            a[step].n++;  //插入的线段匹配则此条线段的记录+1
            return;  //插入结束返回
      }

      //备注:下面这句if语句应该是可以不用的,正常情况下这种情况一定包含在上面的if语句中
      if (a[step].left==a[step].right)   return;   //当前线段树的线段没有儿子,插入结束返回
      int mid=(a[step].left+a[step].right)/2;
      if (mid>=t)    insert(s,t,step*2);   //如果中点在t的右边,则应该插入到左儿子
      else if (mid<s)    insert(s,t,step*2+1);   //如果中点在s的左边,则应该插入到右儿子
      else    //否则,中点一定在s和t之间,把待插线段分成两半分别插到左右儿子里面
      {
            insert(s,mid,step*2);
            insert(mid+1,t,step*2+1);
      }
}

三条已知线段插入过程:

[2,5]

--[2,5]与【0,7】比较,分成两部分:[2,3]插到左儿子【0,3】,[4,5]插到右儿子【4,7】

--[2,3]与【0,3】比较,插到右儿子【2,3】;[4,5]和【4,7】比较,插到左儿子【4,5】

--[2,3]与【2,3】匹配,【2,3】记录+1;[4,5]与【4,5】匹配,【4,5】记录+1

[4,6]

--[4,6]与【0,7】比较,插到右儿子【4,7】

--[4,6]与【4,7】比较,分成两部分,[4,5]插到左儿子【4,5】;[6,6]插到右儿子【6,7】

--[4,5]与【4,5】匹配,【4,5】记录+1;[6,6]与【6,7】比较,插到左儿子【6,6】

--[6,6]与【6,6】匹配,【6,6】记录+1

[0,7]

--[0,7]与【0,7】匹配,【0,7】记录+1

插入过程结束,线段树上的记录如下(红色数字为每条线段的记录n):

                                               【0,7】
                                                    1
                               /                                            \
                     【0,3】                                           【4,7】
                         0                                                     0
                 /                 \                                     /                 \
       【0,1】                 【2,3】                【4,5】                【6,7】
            0                           1                          2                         0
          /    \                      /      \                 /     \                    /      \
 【0,0】 【1,1】       【2,2】 【3,3】     【4,4】 【5,5】     【6,6】 【7,7】
     0            0            0            0           0           1            0           0

询问操作和插入操作类似,也是递归过程,略

2——依次把【0,7】 【0,3】 【2,3】 【2,2】的记录n加起来,结果为2

4——依次把【0,7】 【4,7】 【4,5】 【4,4】的记录n加起来,结果为3

7——依次把【0,7】 【4,7】 【6,7】 【7,7】的记录n加起来,结果为1

不管是插入操作还是查询操作,每次操作的执行次数仅为树的深度——logN

建树有n次插入操作,n*logN,一次查询要logN,m次就是m*logN;总共复杂度O(n+m)*logN,这道题N不超过30000,logN约等于14,所以计算量在10^5~10^6之间,比普通方法快了1000倍;

  评论这张
 
阅读(1593)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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