亟隐

朝不闻道,夕亦死可矣

05/20
08:34
数据结构 算法区

从普通线段树到zkw线段树

鉴于给zkw线段树初学者讲解资料缺乏,在练习后写了详细点的讲解。读者需要掌握普通线段树,且本文是仅仅讲zkw线段树基本操作及懒标记的实现。关于<统计的力量——线段树详细教程>里面讲的区间修改求和的方法另外写着:戳这里

储存结构:指针版线段树要换成数组版。在普通线段树建树时,子树的地址是随意定的,而现在要换成堆式,保证a[p]的子数是a[p*2]和a[p*2+1],也就成了个完全二叉树。假设输入值有n个数,取一个2的多次方数m,使m>=n,这样就确定树叶子的数量,而非叶子部分总共有m-1个。这样输入第i个数存储地址为a[i+m-1]。由于zkw的特性,需要添加第0和第n+1的输入值,并设定为空量(原因下文会提到),所以m改为m-2>=n,而第i个数存储地址也变为a[i+m]。

查询:采用自下而上的方法。对于查询[l,r]区间,zkw查询方式是开区间,即(l-1,r+1),所以从开始查找的位置是l-1+m和r+1+m,以两个叶子开始,不断上升找其父亲节点,直到两个节点相邻,如果左叶子开始寻找的节点是左节点,则同父亲的右节点被[l,r]包含;如果右叶子开始寻找的节点是右节点,则同父亲的左节点被[l,r]包含,代码:

寻找的节点区间互不交叉,且合并后恰好是[l,r]。由于搜索的是开区间,在搜索[1,x]和[x,n]时超越空间,所以在首尾添加个空值。

修改:采用自下而上的方法。对于修改第i个单点,存储位置是a[i+m],所以要修改的从此点开始一直找跟,直到树的根,每个节点更新值。zkw线段树省去了记录左右儿子地址,左右边界,和普通线段树相比,只剩下了一个值,所以zkw使用的是一维数组。现在,可以去找个单点修改的题目做做,理解了zkw线段树后开始懒标记。

懒标记:普通线段树的标记是找到要修改区间包含的节点时,作下标记且更新此点以上节点的值。zkw线段树需要开一个一维数组记录标记值,同样的可以实现这一过程。zkw线段树查找的节点都是被修改区间包含的,然后对于找到的节点,修改值并做标记。向上更新值普通线段树是通过递归实现的,zkw线段树不需要每次找到包含节点时就往上更新,而是从两个最初查找叶子的父亲开始向上更新值,其效果是一样的。
那么,查找时呢?普通线段树是对于当前查找点存在标记且需要查找儿子时才下放标记,zkw线段树查找是两条线上的点,对于这两条线的节点,从根开始自顶而下下放标记。
下面代码为poj3468(区间修改值、询问区间和):

  1. Pingback ACM之杂七杂八 | 诟屍

  2. Pingback writeessay