早早得就学了线段树的一些基础应用，当时急于应用，对它的好多认识都比较肤浅，最近拿起来复习了下，加深了些对它的理解。
我觉得重要的就是要理解，对于一条线段[L R]在线段树中插入或是更新或是查询，它的复杂度为什么是log级别的，我想了两个方法来证明：
1. 对于线段[L R]对node[r].L及node[r].R的覆盖情况，可以分成三种情况，一种是node[r].L及node[r].R被线段[L R]覆盖；一种是node[r].L及node[r].R其中一个端点被[L R]覆盖；最后一种是两个端点都不被覆盖。第一种就直接返回了，第二种到下一层节点的时候，又转变成了第二种的问题，因此复杂度最高是树高，是log级别的，而第三种是可以转换成连个第二种，所以级别也是log级的。
2. 对于一个查询[L R]，观察线段树的叶子节点，找到L及R叶子，线段树的插入、更新、查询动作需要覆盖到L及R，从L及R往root方向走，得到两条树高路径，查询的复杂度肯定小于等于这两条路径和，因此可以得到复杂度是log级别的。
对应之前做过的线段树的简单应用，印象最深刻的有下面几个：
1. 求矩形并的周长；
2. 求矩形并的面积；
3. 区间求和，求极值以及区间更新。
求周长和求面积都需要维护区间的测度这个量，需要标识出某个区间是否被覆盖，左右端点是否被覆盖，甚至被覆盖的次数，通过以上量进行传递和更新。
区间更新想到的两题，一个是这，还一个是关灯问题，查询某个区间内灯量的数目，可以使用的方法是，标记某个区间需要被更新，当查询的时候，将上述覆盖的区间向孩子传递。