zkw线段树 学习笔记

前置知识

  1. C++位运算
  2. 学过线段树(其实关系不大)

什么是zkw线段树

就是一种线段树。(废话) 与普通线段树相比,zkw线段树更快、更短小。 本篇博客讲一个例题:Luogu P3372

普通线段树

zkw线段树

zkw线段树的实现

首先来看一看变量的定义与BuildTree操作

这是一棵求和的线段树(废话) 然后我们发现它有16个叶子节点。 而$16=2^{log_2(16+1)}$ 那我们定义一个N代表叶子节点的数目,n代表原数组的长度。 细心的读者们肯定会发现上面的计算N的方法计算出来为$32$,是$16$的两倍。对,这样对以后有用。

单点修改

直接放代码了QWQ

单点查询

单点查询更简单啦

区间修改

蒟蒻:区间修改复杂度不会很高吗?zkw线段树怎样让他复杂度降低呢? 神犇:直接像线段树那样加一个可持久化标记不就好了吗? 这是一棵树:
比如说要修改区间$[7,14]$。 就是修改这一段区间:
标记$l$为待修改区间的左标记的左边一格,标记$r$为待修改区间的右标记的右边一格。
那么$[7,7]$节点需要$+k\times 1$,同理,$[6,7]$也要$+k\times 1$,以此类推,但是$[8,9]$节点需要$+k \times 2$因为它的两个儿子都修改,而上文提到这是一棵求和线段树,所以需要$\times 2$。那么可知,$[8,11]$需要$+k \times 4$,$[8,15]$需要$+k\times 8$。 问题来了,怎么求$k$的系数呢? 我们可以设$now=1,CountLeft=0,CountRight=0$分别表示本层包含多少个节点、$l$指针从叶子节点走来总共走了多少节点、$r$指针从叶子节点走来总共走了多少节点。那么每向上一次GetFa都需要将$now<<=1$(即:$now*=2$),$l$指针每向上一次GetFa都需要$l>>=1$(即:$l/=2$),$r$指针每向上一次GetFa都需要$r>>=1$(即:$r/=2$)。 注意:这次修改需要到达根节点。

区间查询

与上文的区间修改差不多。只是将修改改成了查询,这里不讲了,直接放代码:

关于例题

对对对,就是Luogu P3372 直接上代码,因为就是区间修改+区间查询:

评论

  1. yzx1798106406 博主

    test

    7月前
    2019-2-27 19:08:32

发送评论


				
上一篇
下一篇