作者 | 京東云開發(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ò)程圖示如下:
我們可以發(fā)現(xiàn),會(huì)先創(chuàng)建默認(rèn)的根節(jié)點(diǎn) tree [1],之后創(chuàng)建出上圖中 tree [2] 和 tree [3] 節(jié)點(diǎn),而此時(shí)并沒有找到區(qū)間 [5, 5],那么需要繼續(xù)創(chuàng)建上圖中的 tree [4] 和 tree [5] 節(jié)點(diǎn)(與直接創(chuàng)建出所有節(jié)點(diǎn)不同,如果是直接創(chuàng)建好所有節(jié)點(diǎn)的話它們的位置應(yīng)該在 tree [6] 和 tree [7]),現(xiàn)在 tree [5] 節(jié)點(diǎn)表示的區(qū)間符合我們要找的條件,可以進(jìn)行賦值和 pushUp 操作了,與直接創(chuàng)建出所有節(jié)點(diǎn)相比,動(dòng)態(tài)開點(diǎn)少創(chuàng)建了 4 個(gè)節(jié)點(diǎn),也就是圖中標(biāo)紅的四個(gè)節(jié)點(diǎn)我們是沒有創(chuàng)建的。 由于每次操作都可能創(chuàng)建并訪問(wèn)全新的一系列節(jié)點(diǎn),因此 m 次單點(diǎn)操作后節(jié)點(diǎn)的空間復(fù)雜度是 O (mlogn),如果我們采用線段樹動(dòng)態(tài)開點(diǎn)解題的話,空間要開的盡可能大,Java 在 128M 可以開到 5e6 個(gè)節(jié)點(diǎn)以上。 結(jié)合圖示大家應(yīng)該能理解動(dòng)態(tài)開點(diǎn)的過(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)推薦
評(píng)論