【线段树】动态开点

使用场景

1. 维护的区间太大以至于 \(4N\) 存不下，通常是权值线段树；
2. 维护的区间下标存在负数；

时间复杂度

1. 全部开点，则 \(O(2N - 1)\)
2. 每递归一次，最多开点 \(O(\log_N)\) ，若调用 \(M\) 次， \(O(M\log_N)\)

原理

1. 若一段子区间 \([L,R]\) 对应的线段树节点为 \(cur\) ，当不需要递归时，就不建点；

2. 当调用 addtag() 时，新建节点。

注意事项