1. 线段树的结构
线段树是个记录区间和区间信息的二叉树，而且是满二叉树去掉几个叶子。根结点是完整的区间，然后不断折半。
这没什么好说的，就只是个存储区间和所求问题信息的二叉树而已。
所谓记录区间，就是指每个树结点要唯一对应一个区间，具体地是记录左端和右端点；
所谓区间信息 or 所求问题信息，就是指每个结点要存储相应区间的一个字段，这个字段往往直接或间接是问题所求的。
例如，我有 1 kw 个元素的整数 int 数组 num[1 to 1 kw]，元素的内容已经被初始化，现在我要进行一个查询，给出一个区间 [L, R], 问区间内所有数之和是多少。
（因为数据太多，求和结果会很大，为了防止数据溢出，一般情况会要求输出结果对某个大数取模，此处不考虑这个；另外，此处问题要求区间和，只是用来举例，也可以是区间最大值、最小值，涉及多维变量还可能是多个值）
这是一个逻辑上很简单的题，因为一次遍历就可以得到结果，但是时间会很长，何况不止一次查询，所以关键是能在短时间内解出此问题。那么线段树就出场了。
线段树记录了多个区间的信息，但并不是区间的幂集，也就是说，并不是记录全部可能子区间，而是有规律的折半记录。
根节点记录 [1, 1kw] 所有数的和，它的左右子结点分别记录了 [1, 500w] 和 [500w+1, 1kw] 所有数的和，按此规律直到遇到叶子，也就是形如 [ 100, 100] 这样的长度为 0 的子区间。
有了这样的树结构，进行区间和查询时，就可以从根节点开始，自顶向下进行搜索，找到某个中间结点子区间 [left, right] 被 [L, R] 包含时，就可以直接返回这个子区间的区间和来参与加法计算。很简单的道理， [L, R] 的区间和 = [left, right] 的区间和 + 另一部分和。
// 简单 query 操作: 在 v 结点代表的区间 [left, right] 中考察 // void query(int v, int left, int right) { if(L <= left && right <= R) { sum += tree[v]; // tree[v] 是 [left, right] 区间元素之和。再次强调，tree[v] 视问题而定，此问题是区间和 } // ... // }
如果 [left, right] 不被 [L, R] 包含，那就再考察 结点 v 的左右两个子树，直到找到被 [L, R] 包含的区间所对应的结点，如上所述进行加和。所以，自顶向下是一个递归的过程，没找到就找，找到了就加。
2. 线段树的关键： 懒标记实现延迟更新
光有线段树的结构并不稀奇，无非就像折半查找一样进行区间查询而已。关键是懒标记实现的延迟更新。
如果区间的元素是静态不动的，那么我们构建好了一棵树就可以一直使用它，如 1. 所述进行查询； 然而现实情况是，区间经常变动，这就需要更新。
而更新也往往是对区间进行的。
倘若是单点更新，某个元素加上 b，那么我们只需要进行 O(logn) 的查找，自顶向下只更新一条路径，这是很简单的。但如果是对一个区间进行更新，[L, R] 中每个数都加上 b，那么如果使用 R - L + 1 次单点更新，就完全体现不出来线段树的优点了。不如说，如果把区间更新写成区间内每个单点更新的循环遍历，那么这就不是个线段树了，退化成普通的查找树了。线段树怎么做？ 每次只进行最少数量的树结点的更新。比如，自顶向下找到了某个结点 v 对应的某个区间 [left, right]，它被 [L, R] 包含，那么这次只更新这个 v 结点的信息，把它的区间和（记住我们的目的依然是查询区间和）加上 b * (right - left +1)，然后在此子树上的更新从此停止，不必实时地更新它的所有后代结点了。因为如果更新，就会使得更新的结点数量过于庞大，使得线段树退化。之所以不必接着更新 v 的后代结点，是因为如果此次更新后，后续来了许多个查询的操作，这些查询的区间都包含着 [left, right], 那么结点 v 完全可以提供本区间的线段和，而不必访问其任何后代结点（如 1. 所述）。
但是更新还是要更新的，这就需要在结点 v 上记录一个懒标记，add_mark[v] = b，表示这个结点更新了，但是它的后续结点没有更新，下次需要使用到 v 的子结点之前，要先更新子结点的区间和 tree[v << 1] 和 tree[v << 1 | 1]。
// void add(int v, int left, int right, int b) { if(L <= left && right <= R) { tree[v] += b * ( right - left + 1); // v 区间和信息更新 add_mark[v] = b; // v 子树结点不再更新，而是做懒标记，后面需要更新时再更新 } // ... // }
突然不想写了。累。
3. 线段树上多个更新操作。比如有加法，有乘法，懒标记也需要有更新策略。
pushdown 之时，须更新懒标记。若记录的字段是 x, y, z三维，定义先乘、转向，后加和。设 k1、 k2 分别是旧的、pushdown下来的乘法标记；(a1,b1,c1）、（a2, b2, c2)分别是旧的、pushdown下来的加和标记；t1、t2分别是旧的、pushdown下来的转向标记。 则新的标记 k = k1 * k2; (a, b, c) = k2 * [a1, b1, c1]t2 + (a2, b2, c2); t = t1 + t2
4. 问题不再只是 1kw，而是比 1kw 更大，可以考虑对线段树的二叉树进行压缩存储，维护一个全局变量 node，每涉及到新的结点的查询和更新的时候，tree[++node]来记录新结点，使用 lchild[]、rchild[] 分别记录 v 的左右结点的下标。
而不是通过 2*v、 2*v + 1 这样耗费空间的方式访问。