快捷導(dǎo)航

C++高級(jí)數(shù)據(jù)結(jié)構(gòu)之線段樹

更新時(shí)間：2022年05月24日 08:45:30 作者：下一站不是永遠(yuǎn)

這篇文章主要介紹了C++高級(jí)數(shù)據(jù)結(jié)構(gòu)之線段樹，文章圍繞主題的相關(guān)資料展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下

前言：

高級(jí)數(shù)據(jù)結(jié)構(gòu)（Ⅲ）線段樹（Segment Tree）
線段樹的原理
樹的創(chuàng)建
單點(diǎn)修改
區(qū)間查找
完整代碼及測(cè)試

高級(jí)數(shù)據(jù)結(jié)構(gòu)（Ⅲ）線段樹（Segment Tree）

線段樹的原理

線段樹是一種二叉搜索樹，對(duì)于線段樹中的每一個(gè)非葉子結(jié)點(diǎn)[a,b]，它的左兒子表示的區(qū)間為[a, (a+b)/2]，右兒子表示的區(qū)間為[(a+b)/2+1, b]。因此線段樹是平衡二叉樹，最后的子節(jié)點(diǎn)數(shù)目為N，即整個(gè)線段區(qū)間的長(zhǎng)度，其空間復(fù)雜度為O(n)。

若對(duì)于一個(gè)數(shù)組使用前綴和數(shù)組保存它的區(qū)間和，那么查找區(qū)間和時(shí)間復(fù)雜度為O(1)，而區(qū)間修改時(shí)間復(fù)雜度為O(n)。使用線段樹可以快速查找或修改某個(gè)區(qū)間的值，時(shí)間復(fù)雜度為O(logN)。

線段樹中每一個(gè)結(jié)點(diǎn)代表一個(gè)區(qū)間，對(duì)于區(qū)間【1， 7】線段樹的結(jié)構(gòu)如下圖

實(shí)例：

class SegmentTree{
private static final int[] tree = new int[1000];
int[] arr;
SegmentTree() {
}
SegmentTree(int[] arr) {
this.arr = arr;
}
//創(chuàng)建樹···
public void buildTree(){}
//單點(diǎn)修改更新樹
public void updateTree(){}
//區(qū)間查找
public void queryTree(){}
}

樹的創(chuàng)建

給定一個(gè)數(shù)組arr = [6, 4, 7, 5, 8, 3 , 9]，創(chuàng)建它對(duì)應(yīng)的線段樹數(shù)組。

對(duì)于一個(gè)結(jié)點(diǎn)k，它的左孩子為2 * k，右孩子為 2 * k + 1，此公式適用于根結(jié)點(diǎn)從1開始。但我們?cè)跀?shù)組中存儲(chǔ)元素時(shí)下標(biāo)通常是從0開始的，即根結(jié)點(diǎn)從0開始，此時(shí)它的左孩子為 2 * k + 1，右孩子為 2 * k + 2。

如下圖所示，數(shù)組arr的長(zhǎng)度為7，由于樹是以2為基數(shù)的，且線段樹中葉子結(jié)點(diǎn)保存的是arr中單個(gè)結(jié)點(diǎn)的值，我們可以將數(shù)組arr的長(zhǎng)度設(shè)想為8 （2 ^ 3 = 8，理解為新添了一個(gè)元素0，這對(duì)區(qū)間和并不影響），此時(shí)它對(duì)應(yīng)的線段樹就是一棵結(jié)點(diǎn)數(shù)為15（1 + 2 + 4 + 8）的滿二叉樹。相應(yīng)的結(jié)點(diǎn)值，映射到數(shù)組tree的值在圖中可清晰的看出。

那么，如何用處程序來創(chuàng)建一棵樹呢？

由于線段樹葉子結(jié)點(diǎn)都是數(shù)組arr中的某一元素，所以我們可以使用兩個(gè)變量low和high來標(biāo)記數(shù)組arr的區(qū)間，

若low == high，此時(shí)令tree[node] = arr[low]，并終止遞歸
否則，將區(qū)間二分，分別計(jì)算左區(qū)間[low, mid]和右區(qū)間[mid +1, high],并在最后更新tree[node]

實(shí)現(xiàn)：

//創(chuàng)建樹
public void buildTree() {
this.buildTree(0, 0, arr.length - 1);
}
private void buildTree(int node, int low, int high) {
if(low == high) {
tree[node] = arr[low];
return;
}
int mid = low + (high - low) / 2;
int lnode = 2 * node + 1;
int rnode = 2 * node + 2;
buildTree(lnode, low, mid);
buildTree(rnode, mid + 1, high);
tree[node] = tree[lnode] + tree[rnode];
}

單點(diǎn)修改

若現(xiàn)在將arr[4]的值修改為1，需要怎樣操作呢？

從下圖綠色標(biāo)出的結(jié)點(diǎn)不難看出其更新過程，先將其所對(duì)應(yīng)的葉子結(jié)點(diǎn)修改，然后繼續(xù)向上修改其父節(jié)點(diǎn)即可。

當(dāng)long==high&&low==index時(shí)更新兩個(gè)數(shù)組的值，否則，縮小區(qū)間，在相應(yīng)的區(qū)間搜索，最后更新結(jié)點(diǎn)和即可，相應(yīng)代碼如下

//單點(diǎn)修改更新樹
public void updateTree(int index, int val) {
this.updateTree(0, 0, arr.length - 1, index, val);
}
private void updateTree(int node, int low, int high, int index, int val) {
if(low == high && low == index) {
arr[index] = val;
tree[node] = val;
return;
}
int mid = low + (high - low) / 2;
int lnode = 2 * node + 1;
int rnode = 2 * node + 2;
if(index >= low && index <= mid) {
updateTree(lnode, low, mid, index, val);
}else {
updateTree(rnode, mid + 1, high, index, val);
}
tree[node] = tree[lnode] + tree[rnode];
}

區(qū)間查找

若現(xiàn)在查找數(shù)組arr區(qū)間和[3,6]，如何利用線段樹呢？

在線段樹中，我們將它的和劃分為兩個(gè)區(qū)間[3]和[4,6]，如圖中的黃色結(jié)點(diǎn)

下面來看看相關(guān)代碼如何實(shí)現(xiàn)，給定一個(gè)查找區(qū)間[L, R]，同樣使用變量low和high維護(hù)對(duì)數(shù)組arr的二分查找邊界

若當(dāng)前區(qū)間low > R 或者 high < L，說明已超出查找范圍，返回0
若[low, high]處于區(qū)間[L, R]內(nèi)，返回當(dāng)前結(jié)點(diǎn)的值tree[node]

然后繼續(xù)在左右區(qū)間查找并保存左右區(qū)間的值sumLeft和sumRight，最后返回sumLeft + sumRight即可

//區(qū)間查找
public int queryTree(int L, int R) {
return this.queryTree(0, 0, arr.length - 1, L, R);
}
private int queryTree(int node, int low,
int high, int L, int R) {
if(low > R || high < L) {
return 0;
}else if(low >= L && high <= R) {
return tree[node];
}
int mid = low + (high - low) / 2;
int lnode = 2 * node + 1;
int rnode = 2 * node + 2;
int sumleft = queryTree(lnode, low, mid, L, R);
int sumRight = queryTree(rnode, mid + 1, high, L, R);
return sumleft + sumRight;
}

完整代碼及測(cè)試

class SegmentTree{
private static final int[] tree = new int[1000];
int[] arr;
SegmentTree() {
}
SegmentTree(int[] arr) {
this.arr = arr;
}
//創(chuàng)建樹
public void buildTree() {
this.buildTree(0, 0, arr.length - 1);
}
private void buildTree(int node, int low, int high) {
if(low == high) {
tree[node] = arr[low];
return;
}
int mid = low + (high - low) / 2;
int lnode = 2 * node + 1;
int rnode = 2 * node + 2;
buildTree(lnode, low, mid);
buildTree(rnode, mid + 1, high);
tree[node] = tree[lnode] + tree[rnode];
}
//單點(diǎn)修改更新樹
public void updateTree(int index, int val) {
this.updateTree(0, 0, arr.length - 1, index, val);
}
private void updateTree(int node, int low, int high, int index, int val) {
if(low == high && low == index) {
arr[index] = val;
tree[node] = val;
return;
}
int mid = low + (high - low) / 2;
int lnode = 2 * node + 1;
int rnode = 2 * node + 2;
if(index >= low && index <= mid) {
updateTree(lnode, low, mid, index, val);
}else {
updateTree(rnode, mid + 1, high, index, val);
}
tree[node] = tree[lnode] + tree[rnode];
}
//區(qū)間查找
public int queryTree(int L, int R) {
return this.queryTree(0, 0, arr.length - 1, L, R);
}
private int queryTree(int node, int low, int high, int L, int R) {
if(low > R || high < L) {
return 0;
}else if(low >= L && high <= R) {
return tree[node];
}
int mid = low + (high - low) / 2;
int lnode = 2 * node + 1;
int rnode = 2 * node + 2;
int sumleft = queryTree(lnode, low, mid, L, R);
int sumRight = queryTree(rnode, mid + 1, high, L, R);
return sumleft + sumRight;
}
//輸出線段樹的值
public void printTree() {
int size = 15; //size值的大小由arr數(shù)組的大小而定
for (int i = 0; i < size; i++) {
System.out.print(tree[i] + " ");
}
System.out.println();
}
}
public class SegmentTreeTest {
public static void main(String[] args) {
int[] arr = {6, 4, 7, 5, 8, 3, 9};
SegmentTree st = new SegmentTree(arr);
//創(chuàng)建線段樹
st.buildTree();
st.printTree();
//>>>42 22 20 10 12 11 9 6 4 7 5 8 3 0 0
//查找區(qū)間[3, 6]
int sum = st.queryTree(3, 6);
System.out.println(sum);
//>>>25
//單點(diǎn)修改更新樹, 令arr[4] = 1
st.updateTree(4, 1);
st.printTree();
//>>>35 22 13 10 12 4 9 6 4 7 5 1 3 0 0
}
}

樹結(jié)點(diǎn)版本：

此版本不使用數(shù)組保存，而是以結(jié)點(diǎn)來保存值，相應(yīng)代碼不難實(shí)現(xiàn)，如下：

import java.util.ArrayDeque;
import java.util.Deque;
class SegNode{
int val;
SegNode lnode;
SegNode rnode;
SegNode(){}
SegNode(int val) {
this.val = val;
}
}
class SegTree{
SegNode root;
int[] arr;
SegTree() {}
SegTree(int[] arr) {
this.arr = arr;
this.bulidTree();
}
//創(chuàng)建樹
public void bulidTree() {
root = this.buildTree(0, arr.length - 1);
}
private SegNode buildTree(int low, int high) {
if(low == high) {
return new SegNode(arr[low]);
}
SegNode node = new SegNode();
int mid = low + (high - low) / 2;
node.lnode = buildTree(low, mid);
node.rnode = buildTree(mid + 1, high);
node.val = node.lnode.val + node.rnode.val;
return node;
}
//單點(diǎn)修改更新樹
public void updateTree(int index, int val) {
root = updateTree(root ,0, arr.length - 1, index, val);
}
private SegNode updateTree(SegNode node, int low, int high, int index, int val) {
if(low == high && low == index) {
arr[index] = val;
node.val = val;
return node;
}
int mid = low + (high - low) / 2;
if(index >= low && index <= mid) {
node.lnode = updateTree(node.lnode, low, mid, index, val);
}else {
node.rnode = updateTree(node.rnode, mid + 1, high, index, val);
}
node.val = node.lnode.val + node.rnode.val;
return node;
}
//查找區(qū)間
public int queryTree(int L, int R) {
return queryTree(root, 0, arr.length - 1, L, R);
}
private int queryTree(SegNode node, int low, int high, int L ,int R) {
if(low > R || high < L) {
return 0;
}else if(low >= L && high <= R) {
return node.val;
}
int mid = low + (high - low) / 2;
int sumLeft = queryTree(node.lnode, low, mid, L, R);
int sumRight = queryTree(node.rnode, mid + 1, high, L, R);
return sumLeft + sumRight;
}
//輸出樹(層次遍歷)
public void printTree() {
Deque<SegNode> queue = new ArrayDeque<SegNode>();
queue.offer(this.root);
while(!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
SegNode node = queue.poll();
System.out.print(node.val + " ");
if(node.lnode != null) queue.offer(node.lnode);
if(node.rnode != null) queue.offer(node.rnode);
}
}
}
}
public class SegmentTreeNodeTest {
public static void main(String[] args) {
int[] arr = {6, 4, 7, 5, 8, 3, 9};
//創(chuàng)建線段樹
SegTree st = new SegTree(arr);
st.printTree();
System.out.println("");
//>>>42 22 20 10 12 11 9 6 4 7 5 8 3
//查找區(qū)間[3, 6]
int sum = st.queryTree(3, 6);
System.out.println(sum);
//>>>25
//單點(diǎn)修改更新樹, 令arr[4] = 1
st.updateTree(4, 1);
st.printTree();
System.out.println("");
>>>35 22 13 10 12 4 9 6 4 7 5 1 3
}
}

到此這篇關(guān)于C++高級(jí)數(shù)據(jù)結(jié)構(gòu)之線段樹的文章就介紹到這了,更多相關(guān)C++線段樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: