笔记汇总

在朴素线段树的使用中，有爆值域的风险。

故而产生了动态开点这一解决方式。

结合建图经验，易知用指针可以解决这类问题（树也是一种图）。

线段树每个点只有两个儿子，定义两个指针会更好查找。

但从整体看，并没有降低空间（线段树的点数太大）

所以 动态开点。

实现

结构体的数组大小最好开到上限（因为询问区间导致的最后建点大小不确定）

注意，动态开点线段树结点结构体两指针都不表示区间（指向下方两个点的编号）

但其它值定义方式一样，操作方式一样。

更新时，要先找到其下两个点（不是结点结构体内的指针）

开点操作类似于$Trie$树，有一个动态编号（建了点的数量）。

这也意味着，在任何操作中都必须有一个由上往下开点的步骤（放开头判断）。

当然，已开过的点不用重复开。