刷完了kuangbin专题的线段树 做一下总结(太艰难了经历了。。。最后一题找了一大堆题解对拍了两天,交了一百多份,心态崩了)
- 单点/区间更新,区间求和/最值,最基础的应用,很多时候也可以用树状数组来做
- 染色/贴海报的问题,其实就是区间更新的问题,然后有些特殊的处理
- 连续区间/区间合并问题,一般是用线段树维护左/右最长和总最长区间,注意PushUp和PushDown的处理
- 多种标记,比如对某个数同时进行加,乘,乘方等处理,注意PushDown和PushUp的标记优先级问题
- 扫描线,三个典型的问题就是求多个矩形的面积并,面积交,周长并,可以拓展到三维的求体积