线段树用于维护区间信息（要求满足结合律）。与树状数组相比，它可以实现的区间修改，还同时支持加、乘操作，更具有通用性。
在最后给出动态开点的线段树。
线段树的建立
线段树是一颗平衡二叉树，母结点代表整个区间的和，越往下区间越小。线段树的每个结点对应一条线段，但并不保证所有的线段都是线段的结点。
每个结点的左右节点编号分别为
和
，如果节点
储存区间
的和，那么子节点分别存储
和
，其中
。
左节点对应的区间长度与右节点数相同或者比之恰好多1。
区间修改
线段树能够实现高效的区间修改是由于其引入了一个懒标记/延迟标记。懒标记的存在使区间修改不再继续递归下去，而去打上一个懒标记，将来要用到他的子区间时，再向下传递。
懒标记如其名，只有要用到子区间时它的子区间才会在向下传递一层（你推他一下他走一步的感觉）。
在进行区间修改时，从最大的区间开始，递归向下处理。递归过程中，记当前节点为，当前区间为
，目标区间为
，我们会遇到三种情况：
- 当前区间于目标区间无交集，此时递归结束。
- 当前区间在目标区间之中，此时更新当前区间，并打上懒标记（此前可能存在标记），递归结束。
- 当前区间与目标区间相交但并不包含在目标之中，将区间进行二分操作，并把懒标记传递给两个子区间（此时可能存在之前的标记），清空当前区间的懒标记，最后继续递归两个子区间。
区间查询
我们此处以查询区间的最大值为例，在递归查询过程中，记当前节点为，当前区间为
，目标区间
，我们会遇到三种情况：
- 当前区间与目标区间无交集，此时递归结束，并返回0。
- 当前区间在目标区间之中，此时递归结束，并返回当前区间的值。
- 当前区间与目标区间相交但并不包含在目标之中，此时再递归的向下进行查询，最后将两个区间中的最大值返回。
代码示例
以Leetcode 731. 我的日程安排表 II为例，使用动态指针实现的动态开点的代码为：
class MyCalendarTwo {
class Node {
int val, add;
Node l, r;
}
int N = (int) 1e9 + 1;
Node root;
public MyCalendarTwo() {
root = new Node();
}
public void update(Node node, int cl, int cr, int l, int r) {
if (l <= cl && cr <= r) {
node.add += 1;
node.val += 1;
return;
}
pushdown(node);
int m = cl + cr >> 1;
if (l <= m) update(node.l, cl, m, l, r);
if (r > m) update(node.r, m + 1, cr, l, r);
pushup(node);
}
public void pushdown(Node node) {
if (node.l == null) node.l = new Node();
if (node.r == null) node.r = new Node();
node.l.add += node.add;
node.l.val += node.add;
node.r.add += node.add;
node.r.val += node.add;
node.add = 0;
}
public void pushup(Node node) {
node.val = Math.max(node.l.val, node.r.val);
}
public boolean query(Node node, int cl, int cr, int l, int r) {
if (l <= cl && cr <= r) return node.val < 2;
pushdown(node);
int m = cl + cr >> 1;
if (l <= m && !query(node.l, cl, m, l, r)) return false;
if (r > m && !query(node.r, m + 1, cr, l, r)) return false;
return true;
}
public boolean book(int start, int end) {
boolean ans = query(root, 0, N, start, end - 1);
if (ans) update(root, 0, N, start, end - 1);
return ans;
}
}
递归过程：
线段树-01.png
题目链接
参考文献：
