线段树 | Comzyh的博客

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

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

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

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

早些日子为了学习线段树,在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 “POJ 2777 Count Color 线段树染色”

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

先考虑一道题: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第一题(话说在机房值日的感觉~~爽！)