全部评论 5

  • 我没记错的话现在是默写时间吧

    4天前 来自 浙江

    0
  • 线段树是什么

    4天前 来自 浙江

    0
  • %%%

    4天前 来自 浙江

    0
    • 谁让你看了

      4天前 来自 浙江

      0
    • 好看

      4天前 来自 浙江

      0
    • 100 篇题解
      默认排序时间排序
      皎月半洒花
      皎月半洒花
      小花
      创建时间:2018-02-17 22:35
      查看文章
      一、简介线段树
      ps: 此处以询问区间和为例。实际上线段树可以处理很多符合结合律的操作。

      比如说加法,a[1]+a[2]+a[3]+a[4]=(a[1]+a[2])+(a[3]+a[4]) 。

      线段树之所以称为“树”,是因为其具有树的结构特性。线段树由于本身是专门用来处理区间问题的(包括 RMQ、RSQ 问题等)。

      对于每一个子节点而言,都表示整个序列中的一段子区间;对于每个叶子节点而言,都表示序列中的单个元素信息;子节点不断向自己的父亲节点传递信息,而父节点存储的信息则是他的每一个子节点信息的整合。

      有没有觉得很熟悉?对,线段树就是分块思想的树化,或者说是对于信息处理的二进制化——用于达到 O(logn) 级别的处理速度,log 以 2 为底。(其实以几为底都只不过是个常数,可忽略)。而分块的思想,则是可以用一句话总结为:通过将整个序列分为有穷个小块,对于要查询的一段区间,总是可以整合成 k 个所分块与 m 个单个元素的信息的并 (0≤k,m≤
      n

      )。但普通的分块不能高效率地解决很多问题,所以作为 log 级别的数据结构,线段树应运而生。

      Extra Tips

      其实,虽然线段树的时间效率要高于分块但是实际上分块的总合并次数不会超过
      n

      但是线段树在最坏情况下的合并次数显然是要大于这个时间效率的。

      但是毕竟也只是一个很大的常数而已。

      However,虽说如此,分块的应用范围还是要广于线段树的,因为虽然线段树好像很快,但是它只能维护带有结合律的信息,比如区间 max/min、∑、xor 之类的,但是不带有结合律的信息就不能维护(且看下文分解);而分块则灵活得多,可以维护很多别的东西,因为实际上分块的本质就是优雅的暴力。

      其实越暴力的算法可以支持的操作就越多、功能性就越强!你看 n
      2
      的暴力几乎什么都可以维护。

      二、逐步分析线段树的构造实现
      1、建树与维护
      由于二叉树的自身特性,对于每个父亲节点的编号 i,他的两个儿子的编号分别是 2i 和 2i+1,所以我们考虑写两个 O(1) 的取儿子函数:

      int n;
      int ans[MAXN*4];
      
      inline int ls(int p){return p<<1;}//左儿子 
      inline int rs(int p){return p<<1|1;}//右儿子 
      

      Extra Tips

      1、此处的 inline 可以有效防止无需入栈的信息入栈,节省时间和空间。

      2、二进制位左移一位代表着数值 ×2,而如果左移完之后再或上 1,由于左移完之后最后一位二进制位上一定会是 0 ,所以 ∣1 等价于 +1 。这个地方更多是为了方便,速度方面理论上是要比 +1 快,但其实编译器会帮你主动干这件事。

      那么根据线段树的服务对象,可以得到线段树的维护:

      void push_up_sum(int p){
      	t[p]=t[lc(p)]+t[rc(p)];
      }//	向上不断维护区间操作 
      
      void push_up_min(int p){//max and min
       t[p]=min(t[lc(p)],t[rc(p)]);
       //t[p]=max(t[lc(p)],t[rc(p)]);             
      }
      

      此处一定要注意,push up 操作的目的是为了维护父子节点之间的逻辑关系。当我们递归建树时,对于每一个节点我们都需要遍历一遍,并且电脑中的递归实际意义是先向底层递归,然后从底层向上回溯,所以开始递归之后必然是先去整合子节点的信息,再向它们的祖先回溯整合之后的信息。(这其实是正确性的证明啦)。

      呐,我们在这儿就能看出来,实际上 push_up 是在合并两个子节点的信息,所以需要信息满足结合律!

      那么对于建树,由于二叉树自身的父子节点之间的可传递关系,所以可以考虑递归建树(emmmm 之前好像不小心剧透了 qwq),并且在建树的同时,我们应该维护父子节点的关系:

      void build(ll p,ll l,ll r)
      {
      if(l==r){ans[p]=a[l];return ;}
      //如果左右区间相同,那么必然是叶子节点啦,只有叶子节点是被真实赋值的
      ll mid=(l+r)>>1;
      build(ls(p),l,mid);
      build(rs(p),mid+1,r);
      //此处由于我们采用的是二叉树,所以对于整个结构来说,可以用二分来降低复杂度,否则树形结构则没有什么明显的优化
      push_up(p);
      //此处由于我们是要通过子节点

      4天前 来自 浙江

      0
  • d

    4天前 来自 浙江

    0

热门讨论