數(shù)據(jù)結(jié)構(gòu)與算法-線段樹
圖片來自慕課網(wǎng)辅柴，liuyubobobo講師的課程“玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu) 從入門到進(jìn)階”
線段樹介紹
有時(shí)候需要對某個(gè)區(qū)間進(jìn)行操作，比如求和伪节、求最大值最/小值等。下面的問題：
有數(shù)組arr = [2,6,3,5,7,1]臀脏，求數(shù)組任意[L, R]區(qū)間上的和虏冻。
最直觀的方法就是對[L, R]區(qū)間遍歷求和肤粱，最差情況時(shí)間復(fù)雜度O(N)。使用線段樹可以達(dá)到O(lg n)的時(shí)間復(fù)雜度厨相。
什么是線段樹领曼？線段樹又叫區(qū)間樹，將某個(gè)區(qū)間用一個(gè)樹結(jié)點(diǎn)表示蛮穿，樹可以像二叉堆那樣用數(shù)組在構(gòu)建庶骄。如下圖所示數(shù)組A的長度是8，根結(jié)點(diǎn)表示整個(gè)區(qū)間践磅，即[0, 7]单刁；根結(jié)點(diǎn)的左孩子表示區(qū)間的左半部分[0, 3]，右孩子表示區(qū)間的右半部分[4, 7]府适。根據(jù)二叉樹的遞歸結(jié)構(gòu)羔飞，對于A[0, 3]和A[4, 7]像上面一樣繼續(xù)構(gòu)建。當(dāng)達(dá)到樹的葉子結(jié)點(diǎn)時(shí)檐春，區(qū)間中只有一個(gè)元素逻淌。
更廣泛的說，線段樹的每個(gè)結(jié)點(diǎn)都表示數(shù)組A的[L, R]區(qū)間疟暖，在樹的葉子結(jié)點(diǎn)處卡儒，L == R，是單元素區(qū)間俐巴，表示數(shù)組中的某一個(gè)元素骨望。
我們要找某個(gè)[L, R]區(qū)間上的某種值（最大、最小窜骄、和）锦募，只需要從對應(yīng)的樹結(jié)點(diǎn)上獲取即可。比如求A[2, 3]的和邻遏，只需要像二叉搜索樹一樣糠亩，從根結(jié)點(diǎn)出發(fā)虐骑、選擇左孩子A[0, 3]再選擇右孩子A[2, 3]返回其值即可。但是樹結(jié)點(diǎn)表示的區(qū)間并不能囊括所有的區(qū)間可能赎线。比如現(xiàn)在要求A[2, 5]的和廷没。其實(shí)可以看作是A[2, 3]和A[4, 5]兩個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)的和，也就是結(jié)果分散在樹中的多個(gè)結(jié)點(diǎn)中垂寥；或者說可以將區(qū)間拆分成多個(gè)子區(qū)間颠黎，不斷拆分，直到能在樹中找到對應(yīng)的區(qū)間滞项，然后將找到的所有結(jié)點(diǎn)的結(jié)果匯總起來即可狭归。因此，要求A[2, 6]其實(shí)就是將A[2, 3]文判、A[4, 5]过椎、A[6]的和匯總起來。
上面元素個(gè)數(shù)是8戏仓，樹的最后一層剛好可以容納下所有的元素疚宇，此時(shí)樹是一棵滿二叉樹。但是如果元素個(gè)數(shù)有10個(gè)的話赏殃，這一層就容納不下了敷待，因此需要再增加一層，如下仁热，此時(shí)樹不是滿二叉樹榜揖，甚至完全二叉樹也不是。但是線段樹是平衡二叉樹股耽。
為了將樹表示成滿二叉樹根盒，可以將null結(jié)點(diǎn)也補(bǔ)上。
我們還看到對于奇數(shù)個(gè)元素的數(shù)組物蝙，區(qū)間不能平均分炎滞，可以固定讓左孩子的區(qū)間比右孩子的區(qū)間小。如上圖中的A[2]和A[3, 4]诬乞。
那么對于n個(gè)元素的數(shù)組册赛，需要多大的空間（包含補(bǔ)上的null結(jié)點(diǎn)）？
根據(jù)滿二叉樹的性質(zhì)震嫉，樹的最后一層結(jié)點(diǎn)個(gè)數(shù)是森瘪，而樹總的結(jié)點(diǎn)樹是
，可以認(rèn)為樹的最后一層結(jié)點(diǎn)個(gè)數(shù)是樹總結(jié)點(diǎn)的一半票堵。
因?yàn)槲覀儾豢紤]往線段樹中添加元素扼睬，因此使用4n大小的靜態(tài)數(shù)組即可，雖然大多數(shù)情況下會有很多null結(jié)點(diǎn)浪費(fèi)了數(shù)組空間悴势，但是能保證在最壞情況下也不至于數(shù)組下標(biāo)越界窗宇。
線段樹的實(shí)現(xiàn)
根據(jù)上面對線段樹的描述措伐，樹的葉子結(jié)點(diǎn)存放的是數(shù)組中的每一個(gè)元素。我們需要一個(gè)data數(shù)組作為傳入數(shù)組的一個(gè)副本军俊，同時(shí)用一個(gè)tree數(shù)組表示線段樹侥加。樹的根結(jié)點(diǎn)使用tree[0],表示了數(shù)組的整個(gè)區(qū)間。對于任何一個(gè)非葉子結(jié)點(diǎn)i,其左孩子在數(shù)組中的2 * i + 1處粪躬，右孩子在數(shù)組中的2 * i + 2處担败。
線段樹的實(shí)現(xiàn)骨架如下
package tree;
import java.util.Arrays;
public class SegmentTree<E> {
/**
* 存放數(shù)據(jù)的數(shù)組
*/
private E[] data;
/**
* 線段樹，使用4n的靜態(tài)空間
*/
private E[] tree;
private int size;
public int size() {
return size;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException(index);
}
return data[index];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < tree.length; i++) {
sb.append(tree[i]);
if (i != tree.length - 1) sb.append(", ");
}
return sb.append("]").toString();
}
}
get方法簡單的返回傳入數(shù)組中index處的元素而已镰官。
現(xiàn)在要將傳入的數(shù)組轉(zhuǎn)換成線段樹提前，以方便對任何區(qū)間進(jìn)行操作。這個(gè)操作可以是求和朋魔，求最大/最小等等岖研。不如實(shí)現(xiàn)一個(gè)接口，讓用戶自己實(shí)現(xiàn)要完成的操作警检。如下Merger接口，對兩個(gè)元素操作返回一個(gè)結(jié)果害淤。
package tree;
public interface Merger<E> {
E merge(E a, E b);
}
來看構(gòu)造方法扇雕，data是傳入的數(shù)組尔邓，Merger就是我們要進(jìn)行的操作地熄。
public SegmentTree(E[] data, Merger<E> merger) {
this.size = data.length;
this.merger = merger;
this.data = Arrays.copyOf(data, data.length);
this.tree = (E[]) new Object[4 * data.length];
buildSegmentTree(0, 0, data.length - 1);
}
比如要求區(qū)間和，匿名內(nèi)部類就可以寫成下面這樣
new Merger<Integer>() {
@Override
public Integer merge(Integer a, Integer b) {
return a + b;
}
});
線段樹的構(gòu)建
構(gòu)造方法中的buildSegmentTree(treeIndex, L, R);方法是關(guān)鍵莹捡。從根結(jié)點(diǎn)開始崭放，遞歸地構(gòu)建線段樹：
- 遞歸終止條件是到樹的葉子結(jié)點(diǎn)哨苛。即區(qū)間的L和R相等時(shí)，此時(shí)區(qū)間中只有一個(gè)元素币砂，將
data[l]或者data[r]值賦給treeIndex處的結(jié)點(diǎn)即可建峭，表示treeIndex處的結(jié)點(diǎn)保存著該單元素區(qū)間的值。 - 否則决摧，遞歸的構(gòu)建左右子樹：先找到當(dāng)前結(jié)點(diǎn)的左亿蒸、右孩子treeIndex，然后將區(qū)間
[l, r]平分成兩部分掌桩，左子樹leftChild表示區(qū)間[l, mid]边锁，右子樹rightChild表示區(qū)間[mid + 1, r]，在這兩個(gè)區(qū)間遞歸的構(gòu)建左右子樹 - 左右子樹構(gòu)建好了之后波岛，可以利用左右孩子的區(qū)間值匯總成根結(jié)點(diǎn)的值（樹的后序遍歷思想）茅坛，因?yàn)楦Y(jié)點(diǎn)的區(qū)間正是左右孩子表示區(qū)間的結(jié)合。
代碼如下
/**
* 構(gòu)建線段樹
* @param treeIndex SegmentTree中以treeIndex為根的樹
* @param l treeIndex對應(yīng)的樹的左區(qū)間
* @param r treeIndex對應(yīng)的樹的右區(qū)間
*/
private void buildSegmentTree(int treeIndex, int l, int r) {
// 葉子結(jié)點(diǎn)则拷，左右區(qū)間一樣贡蓖，index處存放的數(shù)據(jù)是data[l]或者data[r]
if (l == r) {
tree[treeIndex] = data[l];
return;
}
int leftChild = 2 * treeIndex + 1;
int rightChild = leftChild + 1;
int mid = (r - l) / 2 + l;
buildSegmentTree(leftChild, l, mid);
buildSegmentTree(rightChild, mid + 1, r);
// 左右樹建立好后可以針對具體業(yè)務(wù)場景曹鸠，將左右樹結(jié)果“匯總”到當(dāng)前樹結(jié)點(diǎn)中
// 如對區(qū)間求和那么 tree[treeIndex] = tree[leftChild] + tree[rightChild]
// 再如求區(qū)間的最大/最小值 tree[treeIndex] = Math.max(tree[leftChild], tree[rightChild])
tree[treeIndex] = merger.merge(tree[leftChild], tree[rightChild]);
}
線段樹的區(qū)間查詢
這是核心操作，用于查詢區(qū)間[L, R]上的某操作后的值摩梧。
public E query(int queryL, int queryR) {
if (queryL < 0 || queryR < 0 || queryL >= data.length || queryR >= data.length || queryL > queryR) {
throw new IllegalArgumentException("index is illegal");
}
return query(0, 0, data.length - 1, queryL, queryR);
}
/**
* 查詢[queryL, queryR]之間的結(jié)果
* @param treeIndex SegmentTree中以treeIndex為根的樹
* @param l treeIndex對應(yīng)的樹的左區(qū)間
* @param r treeIndex對應(yīng)的樹的右區(qū)間
* @param queryL 查找的左范圍
* @param queryR 查找的右范圍
* @return [queryL, queryR]之間的結(jié)果
*/
private E query(int treeIndex, int l, int r, int queryL, int queryR) {
// 如果查找的區(qū)間剛好樹的區(qū)間對應(yīng)上了物延，直接返回treeIndex處的結(jié)果
if (l == queryL && r == queryR) {
return tree[treeIndex];
}
int leftChild = 2 * treeIndex + 1;
int rightChild = leftChild + 1;
int mid = (r - l) / 2 + l;
// 如果查找的左范圍比mid還大，只需要在右子樹中查找
if (queryL > mid) return query(rightChild, mid + 1, r, queryL, queryR);
// 如果查找的右范圍比mid + 1小仅父，只需要在左子樹中查找
if (queryR < mid + 1) return query(leftChild, l, mid, queryL, queryR);
// 在左右子樹查找并將結(jié)果融合叛薯，將查詢的區(qū)間[queryL，queryR]拆分成：在左子樹中查找[queryL, mid]笙纤，在右子樹中查找[mid + 1, queryR]
return merger.merge(query(leftChild, l, mid, queryL, mid), query(rightChild, mid + 1, r, mid + 1, queryR));
}
如果要查詢的區(qū)間[queryL, queryR]剛好和樹中某個(gè)結(jié)點(diǎn)表示的區(qū)間一樣耗溜，便可以直接返回。否則在其左省容、右子樹中查詢抖拴，如果要查詢的區(qū)間左端點(diǎn)比左子樹的右端點(diǎn)還大，那么無需查詢左子樹腥椒，直接返回右子樹的查詢結(jié)果即可阿宅；類似的，如果要查詢的區(qū)間右端點(diǎn)比右子樹的左端點(diǎn)還小笼蛛，就不必在右子樹中查詢了洒放，直接返回左子樹的查詢結(jié)果即可；否則滨砍，要查詢的區(qū)間覆蓋了左右子樹往湿，需要將[queryL, queryR]拆分成[queryL,mid]和[]需要將左右子樹的結(jié)果匯總。
線段樹的更新
線段樹的更新將除了index處元素更新成e惋戏，由于data數(shù)組改變领追，tree也需要更新。和構(gòu)建線段樹一樣响逢， L == R時(shí)在tree中找到了存放data[index]的結(jié)點(diǎn)绒窑，更新并返回；否則龄句，如果查找的index比mid大回论，說明要更新的結(jié)點(diǎn)在右子樹中，如果比mid + 1小說明要更新的結(jié)點(diǎn)在左子樹中分歇。和在buildSegmentTree中一樣傀蓉，在set方法中更新了葉子結(jié)點(diǎn)的值后，其上直到根結(jié)點(diǎn)的父結(jié)點(diǎn)都需要更新职抡。
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException(index);
}
data[index] = e;
// 接下來更新tree,從根結(jié)點(diǎn)開始
set(0, 0, data.length - 1,index, e);
}
private void set(int treeIndex,int l, int r, int index, E e) {
if (l == r) {
tree[treeIndex] = e;
return;
}
int leftChild = 2 * treeIndex + 1;
int rightChild = leftChild + 1;
int mid = (r - l) / 2 + l;
if (index > mid) set(rightChild, mid + 1, r, index, e);
if (index < mid + 1) set(leftChild, l, mid, index, e);
tree[treeIndex] = merger.merge(tree[leftChild], tree[rightChild]);
}
測試
如下葬燎，對于數(shù)組[2, 3, 5, 6]，求[1, 3]區(qū)間上的和。
public static void main(String[] args) {
Integer[] data = {2, 3, 5, 6};
SegmentTree<Integer> segmentTree = new SegmentTree<>(data, (a, b) -> a + b);
System.out.println(segmentTree.query(1,3)); // 14
segmentTree.set(2, 10);
System.out.println(segmentTree.query(1,3)); // 19
}
set前和是14谱净，set后數(shù)組變成[2, 3, 10, 6]再查詢結(jié)果是19窑邦。
@sunhaiyu
2018.11.24
