線段樹用于維護(hù)區(qū)間信息（要求滿足結(jié)合律）。與樹狀數(shù)組相比，它可以實(shí)現(xiàn)的區(qū)間修改，還同時(shí)支持加、乘操作，更具有通用性。
在最后給出動(dòng)態(tài)開點(diǎn)的線段樹。
線段樹的建立
線段樹是一顆平衡二叉樹，母結(jié)點(diǎn)代表整個(gè)區(qū)間的和，越往下區(qū)間越小。線段樹的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一條線段，但并不保證所有的線段都是線段的結(jié)點(diǎn)。
每個(gè)結(jié)點(diǎn)的左右節(jié)點(diǎn)編號(hào)分別為
和
，如果節(jié)點(diǎn)
儲(chǔ)存區(qū)間
的和，那么子節(jié)點(diǎn)分別存儲(chǔ)
和
，其中
。
左節(jié)點(diǎn)對(duì)應(yīng)的區(qū)間長度與右節(jié)點(diǎn)數(shù)相同或者比之恰好多1。
區(qū)間修改
線段樹能夠?qū)崿F(xiàn)高效的區(qū)間修改是由于其引入了一個(gè)懶標(biāo)記/延遲標(biāo)記。懶標(biāo)記的存在使區(qū)間修改不再繼續(xù)遞歸下去，而去打上一個(gè)懶標(biāo)記，將來要用到他的子區(qū)間時(shí)，再向下傳遞。
懶標(biāo)記如其名，只有要用到子區(qū)間時(shí)它的子區(qū)間才會(huì)在向下傳遞一層（你推他一下他走一步的感覺）。
在進(jìn)行區(qū)間修改時(shí)，從最大的區(qū)間開始，遞歸向下處理。遞歸過程中，記當(dāng)前節(jié)點(diǎn)為，當(dāng)前區(qū)間為
，目標(biāo)區(qū)間為
，我們會(huì)遇到三種情況：
- 當(dāng)前區(qū)間于目標(biāo)區(qū)間無交集，此時(shí)遞歸結(jié)束。
- 當(dāng)前區(qū)間在目標(biāo)區(qū)間之中，此時(shí)更新當(dāng)前區(qū)間，并打上懶標(biāo)記（此前可能存在標(biāo)記），遞歸結(jié)束。
- 當(dāng)前區(qū)間與目標(biāo)區(qū)間相交但并不包含在目標(biāo)之中，將區(qū)間進(jìn)行二分操作，并把懶標(biāo)記傳遞給兩個(gè)子區(qū)間（此時(shí)可能存在之前的標(biāo)記），清空當(dāng)前區(qū)間的懶標(biāo)記，最后繼續(xù)遞歸兩個(gè)子區(qū)間。
區(qū)間查詢
我們此處以查詢區(qū)間的最大值為例，在遞歸查詢過程中，記當(dāng)前節(jié)點(diǎn)為，當(dāng)前區(qū)間為
，目標(biāo)區(qū)間
，我們會(huì)遇到三種情況：
- 當(dāng)前區(qū)間與目標(biāo)區(qū)間無交集，此時(shí)遞歸結(jié)束，并返回0。
- 當(dāng)前區(qū)間在目標(biāo)區(qū)間之中，此時(shí)遞歸結(jié)束，并返回當(dāng)前區(qū)間的值。
- 當(dāng)前區(qū)間與目標(biāo)區(qū)間相交但并不包含在目標(biāo)之中，此時(shí)再遞歸的向下進(jìn)行查詢，最后將兩個(gè)區(qū)間中的最大值返回。
代碼示例
以Leetcode 731. 我的日程安排表 II為例，使用動(dòng)態(tài)指針實(shí)現(xiàn)的動(dòng)態(tài)開點(diǎn)的代碼為：
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
題目鏈接
參考文獻(xiàn)：
