深入理解線段樹：線段樹的區(qū)間修改與懶惰標(biāo)記
作者 | 京東云開發(fā)者-王奕龍
線段樹（Segment Tree）是常用的維護(hù)區(qū)間信息的數(shù)據(jù)結(jié)構(gòu)，它可以在 O (logn) 的時(shí)間復(fù)雜度下實(shí)現(xiàn)單點(diǎn)修改、區(qū)間修改、區(qū)間查詢（區(qū)間求和、區(qū)間最大值或區(qū)間最小值）等操作，常用來(lái)解決 RMQ 問(wèn)題。
RMQ (Range Minimum/Maximum Query) 問(wèn)題是指：對(duì)于長(zhǎng)度為 n 的數(shù)列 A，回答若干詢問(wèn) RMQ (A, i, j) 其中 i, j <= n，返回?cái)?shù)列 A 中下標(biāo)在 i, j 里的最小 (大）值。也就是說(shuō)：RMQ 問(wèn)題是指求區(qū)間最值的問(wèn)題。通常該類型題目的解法有遞歸分治、動(dòng)態(tài)規(guī)劃、線段樹和單調(diào)棧 / 單調(diào)隊(duì)列。
這篇內(nèi)容斷斷續(xù)續(xù)寫了兩周，隨著練習(xí)對(duì)線段樹的理解不斷深入，慢慢地學(xué)習(xí)下來(lái)也不覺得它有多么困難，更多的體會(huì)還是熟能生巧，雖然它起初看上去確實(shí)代碼量大一些，但是我覺得只要大家放平心態(tài)，循序漸進(jìn)的掌握下文中的三部分，也沒什么難的。
1. 線段樹
線段樹會(huì)將每個(gè)長(zhǎng)度不為 1 的區(qū)間劃分成左右兩個(gè)區(qū)間來(lái)遞歸求解，通過(guò)合并左右兩區(qū)間的信息來(lái)求得當(dāng)前區(qū)間的信息。 比如，我們將一個(gè)大小為 5 的數(shù)組 nums = {10, 11, 12, 13, 14} 轉(zhuǎn)換成線段樹，并規(guī)定線段樹的根節(jié)點(diǎn)編號(hào)為 1。用數(shù)組 tree [] 來(lái)保存線段樹的節(jié)點(diǎn)，tree [i] 表示線段樹上編號(hào)為 i 的節(jié)點(diǎn)，圖示如下：
圖示中每個(gè)節(jié)點(diǎn)展示了區(qū)間和以及區(qū)間范圍，tree [i] 左子樹節(jié)點(diǎn)為 tree [2i]，右子樹節(jié)點(diǎn)為 tree [2i + 1]。如果 tree [i] 記錄的區(qū)間為 [a, b] 的話，那么左子樹節(jié)點(diǎn)記錄的區(qū)間為 [a, mid]，右子樹節(jié)點(diǎn)記錄的區(qū)間為 [mid + 1, b]，其中 mid = (a + b) / 2。 現(xiàn)在我們已經(jīng)對(duì)線段樹有了基本的認(rèn)識(shí)，接下來(lái)我們看看區(qū)間查詢和單點(diǎn)修改的代碼實(shí)現(xiàn)。
區(qū)間查詢和單點(diǎn)修改線段樹
首先，我們定義線段樹的節(jié)點(diǎn)：
/**
* 定義線段樹節(jié)點(diǎn)
*/
class Node {
/**
* 區(qū)間和 或 區(qū)間最大/最小值
*/
int val;
int left;
int right;
public Node(int left, int right) {
this.left = left;
this.right = right;
}
}
注意其中的 val 字段保存的是區(qū)間的和。定義完樹的節(jié)點(diǎn)，我們來(lái)看一下建樹的邏輯，注意代碼中的注釋，我們?yōu)榫€段樹分配的節(jié)點(diǎn)數(shù)組大小為原數(shù)組大小的 4 倍，這是考慮到數(shù)組轉(zhuǎn)換成滿二叉樹的最壞情況。
public SegmentTree(int[] nums) {
this.nums = nums;
tree = new Node[nums.length * 4];
// 建樹，注意表示區(qū)間時(shí)使用的是從 1 開始的索引值
build(1, 1, nums.length);
}
/**
* 建樹
*
* @param pos 當(dāng)前節(jié)點(diǎn)編號(hào)
* @param left 當(dāng)前節(jié)點(diǎn)區(qū)間下界
* @param right 當(dāng)前節(jié)點(diǎn)區(qū)間上界
*/
private void build(int pos, int left, int right) {
// 創(chuàng)建節(jié)點(diǎn)
tree[pos] = new Node(left, right);
// 遞歸結(jié)束條件
if (left == right) {
// 賦值
tree[pos].val = nums[left - 1];
return;
}
// 如果沒有到根節(jié)點(diǎn)，則繼續(xù)遞歸
int mid = left + right >> 1;
build(pos << 1, left, mid);
build(pos << 1 | 1, mid + 1, right);
// 當(dāng)前節(jié)點(diǎn)的值是左子樹和右子樹節(jié)點(diǎn)的和
pushUp(pos);
}
/**
* 用于向上回溯時(shí)修改父節(jié)點(diǎn)的值
*/
private void pushUp(int pos) {
tree[pos].val = tree[pos << 1].val + tree[pos << 1 | 1].val;
}我們?cè)诮鋾r(shí)，表示區(qū)間并不是從索引 0 開始，而是從索引 1 開始，這樣才能保證在計(jì)算左子樹節(jié)點(diǎn)索引時(shí)為 2i，右子樹節(jié)點(diǎn)索引為 2i + 1。 build()方法執(zhí)行時(shí)，我們會(huì)先在對(duì)應(yīng)的位置上創(chuàng)建節(jié)點(diǎn)而不進(jìn)行賦值，只有在遞歸到葉子節(jié)點(diǎn)時(shí)才賦值，此時(shí)區(qū)間大小為 1，節(jié)點(diǎn)值即為當(dāng)前區(qū)間的值。之后非葉子節(jié)點(diǎn)值都是通過(guò)pushUp()方法回溯加和當(dāng)前節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)值得出來(lái)的。 接下來(lái)我們看修改區(qū)間中的值，線段樹對(duì)值的更新方法，關(guān)注其中的注釋：
/**
* 修改單節(jié)點(diǎn)的值
*
* @param pos 當(dāng)前節(jié)點(diǎn)編號(hào)
* @param numPos 需要修改的區(qū)間中值的位置
* @param val 修改后的值
*/
private void update(int pos, int numPos, int val) {
// 找到該數(shù)值所在線段樹中的葉子節(jié)點(diǎn)
if (tree[pos].left == numPos && tree[pos].right == numPos) {
tree[pos].val = val;
return;
}
// 如果不是當(dāng)前節(jié)點(diǎn)那么需要判斷是去左或右去找
int mid = tree[pos].left + tree[pos].right >> 1;
if (numPos <= mid) {
update(pos << 1, numPos, val);
} else {
update(pos << 1 | 1, numPos, val);
}
// 葉子節(jié)點(diǎn)的值修改完了，需要回溯更新所有相關(guān)父節(jié)點(diǎn)的值
pushUp(pos);
}
修改方法比較簡(jiǎn)單，當(dāng)葉子節(jié)點(diǎn)值更新完畢時(shí)，我們?nèi)匀恍枰{(diào)用pushUp()方法對(duì)所有相關(guān)父節(jié)點(diǎn)值進(jìn)行更新。 接下來(lái)我們看查找對(duì)應(yīng)區(qū)間和的方法：
/**
* 查找對(duì)應(yīng)區(qū)間的值
*
* @param pos 當(dāng)前節(jié)點(diǎn)
* @param left 要查詢的區(qū)間的下界
* @param right 要查詢的區(qū)間的上界
*/
private int query(int pos, int left, int right) {
// 如果我們要查找的區(qū)間把當(dāng)前節(jié)點(diǎn)區(qū)間全部包含起來(lái)
if (left <= tree[pos].left && tree[pos].right <= right) {
return tree[pos].val;
}
int res = 0;
int mid = tree[pos].left + tree[pos].right >> 1;
// 根據(jù)區(qū)間范圍去左右節(jié)點(diǎn)分別查找求和
if (left <= mid) {
res += query(pos << 1, left, right);
}
if (right > mid) {
res += query(pos << 1 | 1, left, right);
}
return res;
}
該方法也比較簡(jiǎn)單，需要判斷區(qū)間范圍是否需要對(duì)向左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的分別查找計(jì)算。 現(xiàn)在表示區(qū)間和的線段樹已經(jīng)講解完畢了，為了方便大家學(xué)習(xí)和看代碼，我把全量的代碼在這里貼出來(lái)：
public class SegmentTree {
/**
* 定義線段樹節(jié)點(diǎn)
*/
static class Node {
/**
* 區(qū)間和 或 區(qū)間最大/最小值
*/
int val;
int left;
int right;
public Node(int left, int right) {
this.left = left;
this.right = right;
}
}
Node[] tree;
int[] nums;
public SegmentTree(int[] nums) {
this.nums = nums;
tree = new Node[nums.length * 4];
// 建樹，注意表示區(qū)間時(shí)使用的是從 1 開始的索引值
build(1, 1, nums.length);
}
/**
* 建樹
*
* @param pos 當(dāng)前節(jié)點(diǎn)編號(hào)
* @param left 當(dāng)前節(jié)點(diǎn)區(qū)間下界
* @param right 當(dāng)前節(jié)點(diǎn)區(qū)間上界
*/
private void build(int pos, int left, int right) {
// 創(chuàng)建節(jié)點(diǎn)
tree[pos] = new Node(left, right);
// 遞歸結(jié)束條件
if (left == right) {
// 賦值
tree[pos].val = nums[left - 1];
return;
}
// 如果沒有到根節(jié)點(diǎn)，則繼續(xù)遞歸
int mid = left + right >> 1;
build(pos << 1, left, mid);
build(pos << 1 | 1, mid + 1, right);
// 當(dāng)前節(jié)點(diǎn)的值是左子樹和右子樹節(jié)點(diǎn)的和
pushUp(pos);
}
/**
* 修改單節(jié)點(diǎn)的值
*
* @param pos 當(dāng)前節(jié)點(diǎn)編號(hào)
* @param numPos 需要修改的區(qū)間中值的位置
* @param val 修改后的值
*/
private void update(int pos, int numPos, int val) {
// 找到該數(shù)值所在線段樹種的葉子節(jié)點(diǎn)
if (tree[pos].left == numPos && tree[pos].right == numPos) {
tree[pos].val = val;
return;
}
// 如果不是當(dāng)前節(jié)點(diǎn)那么需要判斷是去左或右去找
int mid = tree[pos].left + tree[pos].right >> 1;
if (numPos <= mid) {
update(pos << 1, numPos, val);
} else {
update(pos << 1 | 1, numPos, val);
}
// 葉子節(jié)點(diǎn)的值修改完了，需要回溯更新所有相關(guān)父節(jié)點(diǎn)的值
pushUp(pos);
}
/**
* 用于向上回溯時(shí)修改父節(jié)點(diǎn)的值
*/
private void pushUp(int pos) {
tree[pos].val = tree[pos << 1].val + tree[pos << 1 | 1].val;
}
/**
* 查找對(duì)應(yīng)區(qū)間的值
*
* @param pos 當(dāng)前節(jié)點(diǎn)
* @param left 要查詢的區(qū)間的下界
* @param right 要查詢的區(qū)間的上界
*/
private int query(int pos, int left, int right) {
// 如果我們要查找的區(qū)間把當(dāng)前節(jié)點(diǎn)區(qū)間全部包含起來(lái)
if (left <= tree[pos].left && tree[pos].right <= right) {
return tree[pos].val;
}
int res = 0;
int mid = tree[pos].left + tree[pos].right >> 1;
// 根據(jù)區(qū)間范圍去左右節(jié)點(diǎn)分別查找求和
if (left <= mid) {
res += query(pos << 1, left, right);
}
if (right > mid) {
res += query(pos << 1 | 1, left, right);
}
return res;
}
}
如果要?jiǎng)?chuàng)建表示區(qū)間最大值或最小值的線段樹，建樹的邏輯不變，只需要將 **pushUp ()方法和query ()** 方法修改成計(jì)算最大值或最小值的邏輯即可。
2. 線段樹的區(qū)間修改與懶惰標(biāo)記
如果我們不僅對(duì)單點(diǎn)進(jìn)行修改，也對(duì)區(qū)間進(jìn)行修改，那么在區(qū)間修改時(shí)就需要將當(dāng)前區(qū)間值及包含當(dāng)前區(qū)間的子區(qū)間值都修改一遍，這樣所產(chǎn)生的開銷是沒辦法接受的，因此在這里我們會(huì)使用一種懶惰標(biāo)記的方法來(lái)幫助我們避免這種即時(shí)開銷。 簡(jiǎn)單來(lái)說(shuō)，懶惰標(biāo)記是通過(guò)延遲對(duì)節(jié)點(diǎn)信息的更改，從而減少可能不必要的操作次數(shù)。每次執(zhí)行修改時(shí)，我們通過(guò)打標(biāo)記的方法表明該節(jié)點(diǎn)對(duì)應(yīng)的區(qū)間在某一次操作中被更改，但不更新該節(jié)點(diǎn)的子節(jié)點(diǎn)的信息。實(shí)質(zhì)性的修改則在下一次 **“即將訪問(wèn)（update 或 query）” 到帶有懶惰標(biāo)記節(jié)點(diǎn)的子節(jié)點(diǎn) ** 時(shí)才進(jìn)行。 我們通過(guò)在節(jié)點(diǎn)類中添加 add 字段記錄懶惰標(biāo)記，它表示的是該區(qū)間的子區(qū)間值需要 “變化的大小”（一定好好好的理解），并通過(guò) pushDown 方法 “累加” 到當(dāng)前區(qū)間的兩個(gè)子節(jié)點(diǎn)區(qū)間值中。
只要不訪問(wèn)到當(dāng)前區(qū)間的子區(qū)間，那么子區(qū)間值始終都不會(huì)變化，相當(dāng)于子區(qū)間值的變化量被當(dāng)前節(jié)點(diǎn)通過(guò) add 字段 “持有”
pushDown 方法區(qū)別于我們上文中提到的 pushUp 方法，前者是將當(dāng)前節(jié)點(diǎn)值累計(jì)的懶惰標(biāo)記值同步到子節(jié)點(diǎn)中，而后者是完成子節(jié)點(diǎn)修改后，回溯修改當(dāng)前子節(jié)點(diǎn)的父節(jié)點(diǎn)值，我們能夠根據(jù) Down 和 Up 來(lái)更好的理解這兩個(gè)方法的作用方向和修改范圍。 下面我們一起來(lái)看看過(guò)程和具體的代碼，節(jié)點(diǎn)類如下，增加 add 字段：
static class Node {
int left;
int right;
int val;
int add;
public Node(int left, int right) {
this.left = left;
this.right = right;
}
}
區(qū)間修改
建樹的流程與我們上述的一致，就不在這里贅述了，我們主要關(guān)注區(qū)間修改的過(guò)程，還是以如下初始的線段樹為例，此時(shí)各個(gè)節(jié)點(diǎn)的 add 均為 0：
接下來(lái)我們修改區(qū)間 [3, 5] 且區(qū)間內(nèi)每個(gè)值變化量為 1，過(guò)程如下： 先遍歷節(jié)點(diǎn) 1，發(fā)現(xiàn) [3, 5] 區(qū)間不能將 [1, 5] 區(qū)間完全包含，不進(jìn)行修改，繼續(xù)遍歷節(jié)點(diǎn) 2。節(jié)點(diǎn) 2 依然沒有被區(qū)間 [3, 5] 包含，需要繼續(xù)遍歷節(jié)點(diǎn) 5，發(fā)現(xiàn)該節(jié)點(diǎn)被區(qū)間完全包含，進(jìn)行修改并添加懶惰標(biāo)記值，如下圖所示：
完成這一步驟后需要向上回溯修改 tree [2] 節(jié)點(diǎn)的值：
現(xiàn)在 [3, 5] 區(qū)間中 3 已經(jīng)完成修改，還有 4, 5 沒有被修改，我們需要在右子樹中繼續(xù)遞歸查找，發(fā)現(xiàn) tree [3] 中區(qū)間被我們要修改的區(qū)間 [3, 5] 完全包含，那么需要將這個(gè)節(jié)點(diǎn)進(jìn)行修改并懶惰標(biāo)記，如下，注意這里雖然 tree [3] 節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，但是因?yàn)槲覀儧]有訪問(wèn)到它的子節(jié)點(diǎn)所以無(wú)需同步 add 值到各個(gè)子節(jié)點(diǎn)中：
同樣，完成這一步驟也需要向上回溯修改父節(jié)點(diǎn)的值：
到現(xiàn)在我們的區(qū)間修改就已經(jīng)完成了，根據(jù)這個(gè)過(guò)程代碼示例如下：
/**
* 修改區(qū)間的值
*
* @param pos 當(dāng)前節(jié)點(diǎn)編號(hào)
* @param left 要修改區(qū)間的下界
* @param right 要修改區(qū)間的上界
* @param val 區(qū)間內(nèi)每個(gè)值的變化量
*/
public void update(int pos, int left, int right, int val) {
// 如果該區(qū)間被要修改的區(qū)間包圍的話，那么需要將該區(qū)間所有的值都修改
if (left <= tree[pos].left && tree[pos].right <= right) {
tree[pos].val += (tree[pos].right - tree[pos].left + 1) * val;
// 懶惰標(biāo)記
tree[pos].add += val;
return;
}
// 該區(qū)間沒有被包圍的話，需要修改節(jié)點(diǎn)的信息
pushDown(pos);
int mid = tree[pos].left + tree[pos].right >> 1;
// 如果下界在 mid 左邊，那么左子樹需要修改
if (left <= mid) {
update(pos << 1, left, right, val);
}
// 如果上界在 mid 右邊，那么右子樹也需要修改
if (right > mid) {
update(pos << 1 | 1, left, right, val);
}
// 修改完成后向上回溯修改父節(jié)點(diǎn)的值
pushUp(pos);
}
private void pushDown(int pos) {
// 根節(jié)點(diǎn) 和 懶惰標(biāo)記為 0 的情況不需要再向下遍歷
if (tree[pos].left != tree[pos].right && tree[pos].add != 0) {
int add = tree[pos].add;
// 計(jì)算累加變化量
tree[pos << 1].val += add * (tree[pos << 1].right - tree[pos << 1].left + 1);
tree[pos << 1 | 1].val += add * (tree[pos << 1 | 1].right - tree[pos << 1 | 1].left + 1);
// 子節(jié)點(diǎn)懶惰標(biāo)記累加
tree[pos << 1].add += add;
tree[pos << 1 | 1].add += add;
// 懶惰標(biāo)記清 0
tree[pos].add = 0;
}
}
private void pushUp(int pos) {
tree[pos].val = tree[pos << 1].val + tree[pos << 1 | 1].val;
}
區(qū)間查詢
tree [3] 節(jié)點(diǎn)是有懶惰標(biāo)記 1 的，如果我們此時(shí)查詢區(qū)間 [5, 5] 的值，就需要在遞歸經(jīng)過(guò) tree [3] 節(jié)點(diǎn)時(shí)，進(jìn)行 pushDown 懶惰標(biāo)記計(jì)算，將 tree [6] 和 tree [7] 的節(jié)點(diǎn)值進(jìn)行修改，結(jié)果如下：
最終我們會(huì)獲取到結(jié)果值為 15，區(qū)間查詢過(guò)程的示例代碼如下：
public int query(int pos, int left, int right) {
if (left <= tree[pos].left && tree[pos].right <= right) {
// 當(dāng)前區(qū)間被包圍
return tree[pos].val;
}
// 懶惰標(biāo)記需要下傳修改子節(jié)點(diǎn)的值
pushDown(pos);
int res = 0;
int mid = tree[pos].left + tree[pos].right >> 1;
if (left <= mid) {
res += query(pos << 1, left, right);
}
if (right > mid) {
res += query(pos << 1 | 1, left, right);
}
return res;
}
同樣，為了方便大家學(xué)習(xí)，我把全量代碼也列出來(lái)，我認(rèn)為學(xué)習(xí)線段樹的區(qū)間修改比較重要的點(diǎn)是理解 add 字段表示的含義和 pushDown 方法的作用時(shí)機(jī)，而且需要注意只有線段樹中的某個(gè)區(qū)間被我們要修改的區(qū)間全部包含時(shí)（update 和 query 方法的條件判斷），才進(jìn)行值修改并懶惰標(biāo)記，否則該區(qū)間值只在 pushUp 方法回溯時(shí)被修改。
public class SegmentTree2 {
static class Node {
int left;
int right;
int val;
int add;
public Node(int left, int right) {
this.left = left;
this.right = right;
}
}
Node[] tree;
int[] nums;
public SegmentTree2(int[] nums) {
this.tree = new Node[nums.length * 4];
this.nums = nums;
build(1, 1, nums.length);
}
private void build(int pos, int left, int right) {
tree[pos] = new Node(left, right);
// 遞歸結(jié)束條件
if (left == right) {
tree[pos].val = nums[left - 1];
return;
}
int mid = left + right >> 1;
build(pos << 1, left, mid);
build(pos << 1 | 1, mid + 1, right);
// 回溯修改父節(jié)點(diǎn)的值
pushUp(pos);
}
/**
* 修改區(qū)間的值
*
* @param pos 當(dāng)前節(jié)點(diǎn)編號(hào)
* @param left 要修改區(qū)間的下界
* @param right 要修改區(qū)間的上界
* @param val 區(qū)間內(nèi)每個(gè)值的變化量
*/
public void update(int pos, int left, int right, int val) {
// 如果該區(qū)間被要修改的區(qū)間包圍的話，那么需要將該區(qū)間所有的值都修改
if (left <= tree[pos].left && tree[pos].right <= right) {
tree[pos].val += (tree[pos].right - tree[pos].left + 1) * val;
// 懶惰標(biāo)記
tree[pos].add += val;
return;
}
// 該區(qū)間沒有被包圍的話，需要修改節(jié)點(diǎn)的信息
pushDown(pos);
int mid = tree[pos].left + tree[pos].right >> 1;
// 如果下界在 mid 左邊，那么左子樹需要修改
if (left <= mid) {
update(pos << 1, left, right, val);
}
// 如果上界在 mid 右邊，那么右子樹也需要修改
if (right > mid) {
update(pos << 1 | 1, left, right, val);
}
// 修改完成后向上回溯修改父節(jié)點(diǎn)的值
pushUp(pos);
}
public int query(int pos, int left, int right) {
if (left <= tree[pos].left && tree[pos].right <= right) {
// 當(dāng)前區(qū)間被包圍
return tree[pos].val;
}
// 懶惰標(biāo)記需要下傳修改子節(jié)點(diǎn)的值
pushDown(pos);
int res = 0;
int mid = tree[pos].left + tree[pos].right >> 1;
if (left <= mid) {
res += query(pos << 1, left, right);
}
if (right > mid) {
res += query(pos << 1 | 1, left, right);
}
return res;
}
private void pushDown(int pos) {
// 根節(jié)點(diǎn) 和 懶惰標(biāo)記為 0 的情況不需要再向下遍歷
if (tree[pos].left != tree[pos].right && tree[pos].add != 0) {
int add = tree[pos].add;
// 計(jì)算累加變化量
tree[pos << 1].val += add * (tree[pos << 1].right - tree[pos << 1].left + 1);
tree[pos << 1 | 1].val += add * (tree[pos << 1 | 1].right - tree[pos << 1 | 1].left + 1);
// 子節(jié)點(diǎn)懶惰標(biāo)記
tree[pos << 1].add += add;
tree[pos << 1 | 1].add += add;
// 懶惰標(biāo)記清 0
tree[pos].add = 0;
}
}
private void pushUp(int pos) {
tree[pos].val = tree[pos << 1].val + tree[pos << 1 | 1].val;
}
}
3. 線段樹動(dòng)態(tài)開點(diǎn)
線段樹的動(dòng)態(tài)開點(diǎn)其實(shí)不難理解，它與我們上述直接創(chuàng)建好線段樹所有節(jié)點(diǎn)不同，動(dòng)態(tài)開點(diǎn)的線段樹在最初只創(chuàng)建一個(gè)根節(jié)點(diǎn)代表整個(gè)區(qū)間，其他節(jié)點(diǎn)只在需要的時(shí)候被創(chuàng)建，節(jié)省出了空間。當(dāng)然，我們因此也不能再使用pos << 1?和?pos << 1 | 1?來(lái)尋找當(dāng)前節(jié)點(diǎn)的左右子節(jié)點(diǎn)，取而代之的是在節(jié)點(diǎn)中使用 left 和 right 記錄左右子節(jié)點(diǎn)在 tree [] 中的位置，這一點(diǎn)需要注意：
static class Node {
// left 和 right 不再表示區(qū)間范圍而是表示左右子節(jié)點(diǎn)在 tree 中的索引位置
int left, right;
int val;
int add;
}
我們以區(qū)間 [1, 5] 為例，創(chuàng)建區(qū)間 [5, 5] 為 14 的過(guò)程圖示如下：
/**
* 修改區(qū)間的值
*
* @param pos 當(dāng)前節(jié)點(diǎn)的索引值
* @param left 當(dāng)前線段樹節(jié)點(diǎn)表示的范圍下界
* @param right 當(dāng)前線段樹節(jié)點(diǎn)表示的范圍上界
* @param l 要修改的區(qū)間下界
* @param r 要修改的區(qū)間上界
* @param val 區(qū)間值變化的大小
*/
public void update(int pos, int left, int right, int l, int r, int val) {
// 當(dāng)前區(qū)間被要修改的區(qū)間全部包含
if (l <= left && right <= r) {
tree[pos].val += (right - left + 1) * val;
tree[pos].add += val;
return;
}
lazyCreate(pos);
pushDown(pos, right - left + 1);
int mid = left + right >> 1;
if (l <= mid) {
update(tree[pos].left, left, mid, l, r, val);
}
if (r > mid) {
update(tree[pos].right, mid + 1, right, l, r, val);
}
pushUp(pos);
}
// 為該位置創(chuàng)建節(jié)點(diǎn)
private void lazyCreate(int pos) {
if (tree[pos] == null) {
tree[pos] = new Node();
}
// 創(chuàng)建左子樹節(jié)點(diǎn)
if (tree[pos].left == 0) {
tree[pos].left = ++count;
tree[tree[pos].left] = new Node();
}
// 創(chuàng)建右子樹節(jié)點(diǎn)
if (tree[pos].right == 0) {
tree[pos].right = ++count;
tree[tree[pos].right] = new Node();
}
}
private void pushDown(int pos, int len) {
if (tree[pos].left != 0 && tree[pos].right != 0 && tree[pos].add != 0) {
// 計(jì)算左右子樹的值
tree[tree[pos].left].val += (len - len / 2) * tree[pos].add;
tree[tree[pos].right].val += len / 2 * tree[pos].add;
// 子節(jié)點(diǎn)懶惰標(biāo)記
tree[tree[pos].left].add += tree[pos].add;
tree[tree[pos].right].add += tree[pos].add;
tree[pos].add = 0;
}
}
private void pushUp(int pos) {
tree[pos].val = tree[tree[pos].left].val + tree[tree[pos].right].val;
}
整體的邏輯并不難，新增的 lazyCreate 方法是動(dòng)態(tài)開點(diǎn)的邏輯，需要注意的是執(zhí)行區(qū)間更新時(shí)我們方法的參數(shù)中多了 left 和 right 表示當(dāng)前節(jié)點(diǎn)區(qū)間范圍的參數(shù)，因?yàn)槲覀儸F(xiàn)在的節(jié)點(diǎn)中只保存了左右子節(jié)點(diǎn)的位置，而沒有區(qū)間信息，所以我們需要在參數(shù)中攜帶才行，否則我們沒有辦法判斷當(dāng)前區(qū)間和要找的區(qū)間是否匹配。 我還是將全量代碼放在下面，方便大家學(xué)習(xí)：
public class SegmentTree3 {
static class Node {
// left 和 right 不再表示區(qū)間范圍而是表示左右子節(jié)點(diǎn)在 tree 中的索引位置
int left, right;
int val;
int add;
}
// 記錄當(dāng)前節(jié)點(diǎn)數(shù)
int count;
Node[] tree;
public SegmentTree3() {
count = 1;
tree = new Node[(int) 5e6];
tree[count] = new Node();
}
public int query(int pos, int left, int right, int l, int r) {
if (l <= left && right <= r) {
return tree[pos].val;
}
lazyCreate(pos);
pushDown(pos, right - left + 1);
int res = 0;
int mid = left + right >> 1;
if (l <= mid) {
res += query(tree[pos].left, left, mid, l, r);
}
if (r > mid) {
res += query(tree[pos].right, mid + 1, right, l, r);
}
return res;
}
/**
* 修改區(qū)間的值
*
* @param pos 當(dāng)前節(jié)點(diǎn)的索引值
* @param left 當(dāng)前線段樹節(jié)點(diǎn)表示的范圍下界
* @param right 當(dāng)前線段樹節(jié)點(diǎn)表示的范圍上界
* @param l 要修改的區(qū)間下界
* @param r 要修改的區(qū)間上界
* @param val 區(qū)間值變化的大小
*/
public void update(int pos, int left, int right, int l, int r, int val) {
// 當(dāng)前區(qū)間被要修改的區(qū)間全部包含
if (l <= left && right <= r) {
tree[pos].val += (right - left + 1) * val;
tree[pos].add += val;
return;
}
lazyCreate(pos);
pushDown(pos, right - left + 1);
int mid = left + right >> 1;
if (l <= mid) {
update(tree[pos].left, left, mid, l, r, val);
}
if (r > mid) {
update(tree[pos].right, mid + 1, right, l, r, val);
}
pushUp(pos);
}
// 為該位置創(chuàng)建節(jié)點(diǎn)
private void lazyCreate(int pos) {
if (tree[pos] == null) {
tree[pos] = new Node();
}
// 創(chuàng)建左子樹節(jié)點(diǎn)
if (tree[pos].left == 0) {
tree[pos].left = ++count;
tree[tree[pos].left] = new Node();
}
// 創(chuàng)建右子樹節(jié)點(diǎn)
if (tree[pos].right == 0) {
tree[pos].right = ++count;
tree[tree[pos].right] = new Node();
}
}
private void pushDown(int pos, int len) {
if (tree[pos].left != 0 && tree[pos].right != 0 && tree[pos].add != 0) {
// 計(jì)算左右子樹的值
tree[tree[pos].left].val += (len - len / 2) * tree[pos].add;
tree[tree[pos].right].val += len / 2 * tree[pos].add;
// 子節(jié)點(diǎn)懶惰標(biāo)記
tree[tree[pos].left].add += tree[pos].add;
tree[tree[pos].right].add += tree[pos].add;
tree[pos].add = 0;
}
}
private void pushUp(int pos) {
tree[pos].val = tree[tree[pos].left].val + tree[tree[pos].right].val;
}
}
編輯：黃飛
-
編程
+關(guān)注
關(guān)注
88文章
3544瀏覽量
93492 -
代碼
+關(guān)注
關(guān)注
30文章
4700瀏覽量
68108
原文標(biāo)題：深入理解線段樹
文章出處：【微信號(hào)：OSC開源社區(qū)，微信公眾號(hào)：OSC開源社區(qū)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
深入理解和實(shí)現(xiàn)RTOS_連載
CAD怎么連接線段？CAD線段連接教程
對(duì)棧的深入理解
為什么要深入理解棧
基于幾何約束的視頻幀間線段特征匹配算法
基于線段樹的內(nèi)存管理方法
工商網(wǎng)監(jiān)
評(píng)論