动态线段树是什么。。。先%一波。。。。
by Little_Jian @ 2017-12-04 17:10:08
很显然有的
by zj余能 @ 2017-12-04 18:11:11
@[Little\_Jian](/space/show?uid=30694) 我也……不知道啊……（能一边加点一边建树吗……（先%%%csh再说
by _Ts_ @ 2017-12-07 15:39:20
@[zj余能](/space/show?uid=20360) orz能稍微讲讲嘛？
by _Ts_ @ 2017-12-07 15:39:47
@[\_Ts\_](/space/show?uid=48415) 貌似可以一边向下递归一边动态开点。。。。
不过差别不大吧。。。。。。
一开始建树的大小定的还是最大值。。。只是没有占内存。。。
这题正解不是单调栈吗。。。。
by Little_Jian @ 2017-12-07 15:50:43
朴素动态开点就是这样的：
传统线段树的搞法一般都是建了一棵完全二叉树，其中编号为 $x$ 的节点的左右儿子编号分别为 $x \times 2$ ， $x \times 2 +1$。
显然这么做的空间复杂度是 $O(n)$ 的，确切的说点的编号最大是 $4n-5$ ，在区间很大的时候就不行了。
那怎么办呢？ 考虑到线段树上每次区间操作最多找到 $log_n$ 个区间，当操作个数相对较少 （ $10^5$ 左右）的时候，显然不是线段树上的每个节点都会被访问到的。
所以可以先不记录这些节点的编号，当我们访问到一个没有访问过的节点时，为这个节点赋予一个新的编号。
具体一点，对于点 $x$ ，$ch[x][2]$ 数组代表这个节点的左右两个儿子，当我们需要访问某个儿子时，若这个儿子为空（即为0） ，则将它的编号设置为一个没有出现过的编号。
这样的话空间复杂度就是 $O(nlog_m)$ 的了，其中 $n$ 为操作次数， $m$ 为序列长度。
by 消失的海岸线 @ 2017-12-07 16:34:03
啊，我这个菜逼口胡的，说错了请大力骂我。
by 消失的海岸线 @ 2017-12-07 16:37:32
@[消失的海岸线](/space/show?uid=30459) 然而动态开点就写不了ZKW线段树了。。。T\_T
不会传统线段树 QwQ
by Little_Jian @ 2017-12-07 16:37:58
@[Little\_Jian](/space/show?uid=30694) ZKW不资词动态开点，局限性还是蛮大的= =
by 消失的海岸线 @ 2017-12-07 16:41:53
@ \_Ts\_ 您可以维护区间最大值，然后在序列末尾插入一个数，相当于单点Modify。这样写显然可以用zkw
by zj余能 @ 2017-12-08 21:28:38