線段樹用于維護區(qū)間信息（要求滿足結合律）。與樹狀數(shù)組相比塞关，它可以實現(xiàn)的區(qū)間修改，還同時支持加墩新、乘操作马澈，更具有通用性瓢省。
在最后給出動態(tài)開點的線段樹。
線段樹的建立
線段樹是一顆平衡二叉樹痊班，母結點代表整個區(qū)間的和勤婚，越往下區(qū)間越小。線段樹的每個結點對應一條線段涤伐，但并不保證所有的線段都是線段的結點馒胆。
每個結點的左右節(jié)點編號分別為
和
，如果節(jié)點
儲存區(qū)間
的和凝果，那么子節(jié)點分別存儲
和
祝迂，其中
。
左節(jié)點對應的區(qū)間長度與右節(jié)點數(shù)相同或者比之恰好多1器净。
區(qū)間修改
線段樹能夠實現(xiàn)高效的區(qū)間修改是由于其引入了一個懶標記/延遲標記型雳。懶標記的存在使區(qū)間修改不再繼續(xù)遞歸下去，而去打上一個懶標記山害，將來要用到他的子區(qū)間時纠俭，再向下傳遞。
懶標記如其名浪慌，只有要用到子區(qū)間時它的子區(qū)間才會在向下傳遞一層（你推他一下他走一步的感覺）柑晒。
在進行區(qū)間修改時，從最大的區(qū)間開始眷射，遞歸向下處理匙赞。遞歸過程中，記當前節(jié)點為妖碉，當前區(qū)間為
涌庭，目標區(qū)間為
，我們會遇到三種情況：
- 當前區(qū)間于目標區(qū)間無交集欧宜，此時遞歸結束坐榆。
- 當前區(qū)間在目標區(qū)間之中，此時更新當前區(qū)間冗茸，并打上懶標記（此前可能存在標記）席镀，遞歸結束匹中。
- 當前區(qū)間與目標區(qū)間相交但并不包含在目標之中，將區(qū)間進行二分操作豪诲，并把懶標記傳遞給兩個子區(qū)間（此時可能存在之前的標記）顶捷，清空當前區(qū)間的懶標記，最后繼續(xù)遞歸兩個子區(qū)間屎篱。
區(qū)間查詢
我們此處以查詢區(qū)間的最大值為例服赎，在遞歸查詢過程中，記當前節(jié)點為交播，當前區(qū)間為
重虑，目標區(qū)間
，我們會遇到三種情況：
- 當前區(qū)間與目標區(qū)間無交集秦士，此時遞歸結束缺厉，并返回0。
- 當前區(qū)間在目標區(qū)間之中隧土，此時遞歸結束芽死，并返回當前區(qū)間的值。
- 當前區(qū)間與目標區(qū)間相交但并不包含在目標之中次洼，此時再遞歸的向下進行查詢关贵，最后將兩個區(qū)間中的最大值返回。
代碼示例
以Leetcode 731. 我的日程安排表 II為例卖毁，使用動態(tài)指針實現(xiàn)的動態(tài)開點的代碼為：
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
題目鏈接
參考文獻：
