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

樹的創(chuàng)建

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

對于一個結點k，它的左孩子為2 * k，右孩子為 2 * k + 1，此公式適用于根結點從1開始。但我們在數組中存儲元素時下標通常是從0開始的，即根結點從0開始，此時它的左孩子為 2 * k + 1，右孩子為 2 * k + 2。

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

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

由于線段樹葉子結點都是數組arr中的某一元素，所以我們可以使用兩個變量low和high來標記數組arr的區(qū)間，

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

實現：

//創(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];
}

單點修改

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

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

當long==high&&low==index時更新兩個數組的值，否則，縮小區(qū)間，在相應的區(qū)間搜索，最后更新結點和即可，相應代碼如下

//單點修改更新樹
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ū)間查找

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

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

下面來看看相關代碼如何實現，給定一個查找區(qū)間[L, R]，同樣使用變量low和high維護對數組arr的二分查找邊界

若當前區(qū)間low > R 或者 high < L，說明已超出查找范圍，返回0
若[low, high]處于區(qū)間[L, R]內，返回當前結點的值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;
}

完整代碼及測試

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];
}
//單點修改更新樹
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數組的大小而定
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
//單點修改更新樹, 令arr[4] = 1
st.updateTree(4, 1);
st.printTree();
//>>>35 22 13 10 12 4 9 6 4 7 5 1 3 0 0
}
}

樹結點版本：

此版本不使用數組保存，而是以結點來保存值，相應代碼不難實現，如下：

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;
}
//單點修改更新樹
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
//單點修改更新樹, 令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
}
}

到此這篇關于C++高級數據結構之線段樹的文章就介紹到這了,更多相關C++線段樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: