线段树 Interval Tree，又称区间树 Segment Tree，其中每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。，因而常用于解决数列维护问题，它基本能保证每个操作的复杂度为O(lgN)。

特点

  • 每个区间的长度是区间内整数的个数
  • 叶子节点长度为1，不能再往下分
  • 若一个节点对应的区间是[a,b],则其子节点对应的区间分别是[a,(a+b)/2]和[ (a+b)/2+1,b]
  • 线段树的平分构造，实际上是用了二分的方法。线段树是平衡树，它的深度为log2(b-a+1)
  • 线段树把区间上的任意一条线段都分成不超过2logL条线段

构建

可以用二叉树结构，也可以用数组（数组的大小是长度的4倍）

操作

用线段树解题，关键是要想清楚每个节点要存哪些信息（当然区间起终点，以及左右子节点指针是必须的），以及这些信息如何高效更新，维护，查询。不要一更新就更新到叶子节点，那样更新效率最坏就可能变成O(n)的了。

增加延迟标记，每个结点新增加一个标记，记录这个结点是否被进行了某种修改操作(这种修改操作会影响其子结点)。对于任意区间的修改，我们先按照查询的方式将其划分成线段树中的结点，然后修改这些结点的信息，并给这些结点标上代表这种修改操作的标记。在修改和查询的时候，如果我们到了一个结点p，并且决定考虑其子结点，那么我们就要看看结点p有没有标记，如果有，就要按照标记修改其子结点的信息，并且给子结点都标上相同的标记，同时消掉p的标记。

例题1：POJ 3264 Balanced Lineup 给定Q (1 ≤ Q ≤ 200,000)个数A1,A2 … AQ,多次求任一区间Ai – Aj中最大数和最小数的差。(此题可以用动态规划RMQ法做，更加快速)

例题2：POJ 3468 A Simple Problem with Integers 给定Q (1 ≤ Q ≤ 100,000)个数A1,A2 … AQ,以及可能多次进行的两个操作:1) 对某个区间Ai … Aj的个数都加n(n可变）2) 求某个区间Ai … Aj的数的和

离散化

有时，区间的端点不是整数，或者区间太大导致建树内存开销过大MLE ,那么就需要进行“离散化”后再建树。

POJ 2528 Mayor’s posters 给定一些海报，可能互相重叠，告诉你每个海报宽度（高度都一样）和先后叠放次序，问没有被完全盖住的海报有多少张。

POJ 1151 Atlantis 给定一些矩形，其顶点坐标是浮点数，可能互相重叠，问这些矩形覆盖到的面积是多大。

优化 ZKW

清华张昆玮，自底向上，非递归

参考:

http://dongxicheng.org/structure/segment-tree/

http://poj.org/summerschool/1_interval_tree.pdf

http://blog.csdn.net/metalseed/article/details/8039326