线段树

在一维数组中以完全二叉树方式存储线段树的空间分析

我们大家存储线段树的方式无非两种:

  1. 二叉链表
  2. 一维数组完全二叉树

二叉链表优点是节省空间,缺点是编程复杂度大,执行效率较低,空间复杂度为2N

在一维数组以完全二叉树方式存储线段树的编程复杂度小,执行效率较高,但浪费空间
长期以来,我和我校的OIer一直不知以一维方式存储线段树到底需要开多大的数组.今天正好有些闲暇的时间,写了个小程序,分析了下一维线段树在一维方式存储下到底需要占用多少空间.经本文所述方式计算约为4N

Continue reading

POJ 2777 Count Color 线段树染色

早些日子为了学习线段树,在Du神牛的带领下,做了此题,入门好题也! poj2777 Count Color

此题是本人线段树第二题,前一道是TYVJ1039 忠诚2(一道动态RMQ问题)

输入区间长度L (1 <= L <= 100000),颜色数目 T (1 <= T <= 30) 和 指令数O (1 <= O <= 100000)

接下来O行C x y z 代表将[x,y]区间染成z色,P x y z 代表询问[x,y]有多少种颜色,起始各处颜色为1;

我第一眼看到”1 <= T <= 30″就格外激动为啥不是40呢?显然是为了小于32,所以显然可以用二进制每位表达一种颜色,颜色1是1(0x1)颜色10就是1024(0x400),在线段树里查询便可以获得这一段的几种颜色然后做一次OR操作便可得到所有颜色

我看到T的范围就马上想到到了Matrix67牛的一个位运算优化:位运算简介及实用技巧(二):进阶篇(1)计算二进制中的1的个数的方法
Continue reading

动态RMQ问题(区间最值)的O(LogN)线段树解法–TYVJ1039忠诚2

关于静态不修改元素的O(1)查询的RMQ (Range Minimum/Maximum Query)算法区间最大最小值参见我(Comzyh)另一篇文章

用于求区间最值(RMQ问题)的O(1)算法–ST算法

先考虑一道题:TYVJ1039 忠诚2 (看不了的本文末尾有题)

话说TYVJ总是喜欢出这么赤裸裸的算法题,我也喜欢。

很显然 m(m<=100000)笔账,n表示有n个问题,n<=100000 \( \Theta ( N^{2})\)的算法必然是不行的

话说ST(Sparse Table)算法不是查询O(1)么?ST算法的结构表明,ST的查询复杂度永远是O(1)的,但是动态修改基本上每次是O(NlogN)小点的,对于小更新量还可以,大量修改就不行了,事实证明,我写的动态ST算法超时3点。

这时,线段树的修改(Log N)优势就体现出来了。(因为本题更新的是,比较特殊,是logN)

修改(Insert)时由顶而下以类似二分的方法找到最下面,然后回溯,比较刚更新的点与另一子树,求Min,更新为当前线段的Min值
这个模型比染色用的线段树简单多了,于是它成了我线段树AC第一题(话说在机房值日的感觉~~爽!)

贴之代码:
Continue reading