笔记汇总
即保存历史版本的线段树。
由于这类线段树大小不固定，所以要动态开点。
若是将每个历史版本看作阶段，可以联系到 DP（或者说由旧信息转移到新信息的过程）
由线段树时间复杂度证明可知，一次修改至多影响 log2n 个点。
可以接受（不得不接受）。
实现
因为，我们不能抛弃修改前的信息，所以得将改变信息另外储存起来，
改变了的信息，可以在由上往下转移时寻找。
这意味着我们要两个移动指针（朴素时只有一个）。
一个结点指的是旧值，若被更新了（不改变旧值），则还有一个结点会开点表示新值。
同时，不是在原树上往下动态开点了（而是在另一个指针处开）。
注意，指针不是值，两指针可指向同一节点，也可指向不同节点，
只有指向节点为空时才会开点（用来储存改变信息），
最后由下往上，依托子节点（不只新节点）为当前新节点更新附加值。
当然，要记录不同历史版本的根节点（肯定会新建（单查除外，不过可以处理））。
标记永久化
如果区间修改，我们需要将信息下传，而这，会覆盖大量结点。
每次修改操作我们还得在之前基础上建一棵新树，空间复杂度过高。
如果我们将标记下传呢？
要是修改了一段区间，我们将其中一段附上懒标记，等到查询时，
我们还需要将这份标记下传（不能影响非当前版本），所以要预先处理，这将导致空间爆表。
但要是标记永久化，
我们则不需要下传标记，而是在查询时顺带带上。
其实标记永久化也有懒标记的思想，但重点是它与原结点分离。
