实话实说，作为半个 ACM 选手，不会线段树，实在是有些说不过去。那么问题来了：“线段树都不会，你这 ACM 怎么过的题？怕是签到都难哦。”
但是问题不大，ACM 是多人游戏。我有队友。
以往的的确确，碰到线段树就让队友写，他键盘敲得飞快，我和另外一个队友就想思路，然后线段树先生负责给我们提供所需要的线段树。于是就一直懒得去学。
但是现在，我们走上了不同的道路，ACM 已成回忆或者遗憾，而我必须能够独当一面。
概述
线段树，一般用于区间修改以及查询的需求，以 O(log n) 的查询时间和修改时间闻名于整个算法竞赛世界。
算法竞赛中一般用数组建树，写起来比较方便。思路在各大博客性质的网站上随处可见，不作赘述。但是对于其更新、下放 lazy 以及查询上，我倒是有一些个人体会，于是单开一篇博客，作文以记之。
查询
查询操作，除了查询的区间之外，还会指明查询哪个线段树结点。
我的习惯是，如果结点有 lazy 标记的话，先要更新结点的值，并且下放 lazy，然后再查询该结点。
这样一来有一些好处，首先是更新操作更加随意，可以直接写 lazy，把针对叶子结点的 guard 放到查询上；二来可以直接用 node.val 的值，因为在使用前已经更新了，是正确的值。
随后就是常规操作，即先判断俩区间的关系，如果结点区间被包含，那么直接返回 val 即可。否则分成两部分往子结点查询。
这里就有一个要考虑的地方：我需要直接计算更新后的 val 值，而不依赖子结点的回传。
为什么呢？如果需要回传，那么每一层调用都需要等待回传，最终一定会调用到叶子结点。这线段树就完全退化了，等于没写。
这也确定了哪些问题可以使用线段树而哪些不行。如果我想用线段树，首先我需要找到一个函数，输入结点代表的区间，输入当前的 val，输入 lazy 标记（或者我可以设定很多的或者经过巧妙运算的 lazy 标记），可以正确输出更新后的 val。
这样的函数对于 val 为区间和，lazy 表示区间所增加（变化）的数值时，是这样的：
1 | int f(Node node) { |
对于 val 为区间和，lazy 表示区间所赋值的数值时，是这样的：
1 | int f(Node node) { |
对于 val 为区间最值，lazy 表示区间所增加的数值时，是这样的：
1 | int f(Node node) { |
更新
更新操作也是类似，根据两个区间的关系来决定自己的行为。
当所需要更新的区间包含了结点所代表的区间时，直接改写 lazy 标记。这里就用到查询行为首先下放 lazy 的好处了。
与查询操作的分歧在这个地方：如果不包含，那么当然要去更新子结点。问题在于这个时候我没有办法来仅仅依靠当前结点来计算变化后的值了，我必须等待子结点处理完成，然后通过子结点来更新当前结点的 val。
当然，为了方便，可以直接调用 query 函数来更新 node.val。
还有一个需要注意的地方在于，如果两个区间没有交集，那么最好是立即返回。虽然继续搜索下去对最终结果没有什么影响，因为现在是没有交集的那么和子结点之间当然也是没有交集的，那么最终肯定是一个无效的返回或者说一个对最终结果没有影响的返回。但是，这样一来，每个分支都会搜索到叶子结点，这个操作退化到 O(n) 了，这是不能接受的。