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