zkw线段树

非递归线段树

对于单纯的RMQ问题

我们可以选择ST表这种优秀的算法

但是RMQ问题如果一旦变形.

从原来的单纯的ST表就能解决的问题变成了需要修改的

对于十万级别的数据,ST表没有办法解决这种问题

所以一旦升级到单纯的区间查询区间修改

ST表就会被pass

树状数组?

如果需要维护区间最大值最小值呢?

我们可以选择一种比树状数组更难实现的数据结构

常数比树状数组大

比树状数组更难实现更难一次写对

但是可以拓展的多.

线段树的博客可以参考我之前的博客


我们需要维护三种操作,加减乘,数列长度20W,操作20W次.

三标记线段树?

我们需要维护区间面积交、并,矩形共100个

线段树+扫描线+离散化?

我们需要维护两个信息的最值问题

二维线段树?

我们需要维护一段数列的逆序对的个数

权值线段树?

我们需要维护区间第k大

主席树?

替罪羊树?树套树?可持久化?LCT?


是不是可以说明线段树是高级数据结构的基础?

…但是我水了一个星期的线段树还是没学可持久化和树套树….

对于线段树常数大的问题.

我们可以让他不递归

选择一种更加简易的实现方法

换一种思路去实现和线段树一样的操作.


zkw线段树.

how to build?

线段树堆式储存.

如果我们把它变成二进制呢

可以看到一些奇奇怪怪的规律???

  • 一个节点的父节点是这个数左移1,即x >> 1
  • 一个节点的子节点是这个数右移1,即x << 1
  • 同一层的节点是一次递增的,第n层有\(2^{n-1}\)个节点
  • 最后一层有多少节点,值域就是多少

我们需要建一种不递归就可以完成线段树操作的线段树.

我们直接开够空间,浪费就浪费了.

比如我们维护的序列大小为4.

就会把数据存在tr[5-8]这4个数字里面

那怎么维护父节点信息?

我们是倒叙访问的.所以每次在访问这个点的时候这个点的子节点都处理过了.对于父节点信息直接维护就好了.

维护区间和

维护区间最大最小值

这样我们就可以构建出zkw线段树了.

(*^▽^*)

易于实现好写.


单点查询

我们需要用到差分思想,也就是通过前缀和维护然后做差不就得到了这个点信息了~

查询就…

真的很像树状数组的lowbit的操作.但是与lowbit不同.实现功能多当然不同啊摔


区间

区间查询和,首先我们需要把[l,r]这个闭区间换成(l,r)开区间来算.

啥啥啥这都一堆啥玩意???

我们需要把[l,r]闭区间换成(l,r)开区间来算,不然可能会访问到无效节点.

对于区间操作.我们的实现方式有很多.

最后发现如果不用前缀和维护的话,直接打标记也是可以的…

因为由底至顶更新,所以是先算再传标记.与一般的线段树有一点点区别.\(s\)表示和,\(num\)表示这个点的值.

我们把闭区间换成开区间的方法很多,直接传值的时候\(l-1,r+1\)也是可以的


对于读入,不变

但是需要遍历所有的节点以便总结父节点的信息.


区间修改

闭区间转化成开区间

然后修改对应节点的值.每次左右指针直接跳到父亲节点的就好了

如果两个指针重合了就跳出.

更新的时候及时更新\(lazy\)标记(如果是通过标记修改的话)

标记在上面打完了但是要修改\(sum\)到顶才可以.

\(numx,numy\)表示本次修改中,下面被修改了多少点.


区间查询

\(lazy\)标记正常传递就可以了,因为\(zkw\)线段树的特殊性,所以可以理解为标记向上传递????….

剩下都是一样的操作.

多写写也是挺好写的.


据说常数特别小???

一样的题,一般的线段树跑了316ms,\(zkw\)跑了244ms….

我感觉还不错?

luogu3372_线段树模板1


By:Wahacer

2017.12.25

11:25

发表评论

电子邮件地址不会被公开。 必填项已用*标注