原文鏈接：https://www.cnblogs.com/ctjcalc/p/post2.html

線段樹是一種高效的資料結構，可以在$O(nlog_{2}n)$的時間內查詢區間最值或區間和，解決動態的RMQ問題，并且可以為一些演算法進行優化，如Dijkstra最短路、掃描線等，

實作原理

Copyright ? 2019 ctjcalc，轉載請注明URL，并給出原文鏈接，謝謝，線段樹是一種基于分治演算法的二叉樹，每個結點維護一個區間，以及在該區間內的資料資訊，在當前結點$x$，它的區間是$[left,right]$，則它的兩個子結點的區間分別為$[left,mid],[mid+1,right]$，$mid=\frac{left+right}{2}$，由于采用了分治的思想，在進行操作時每一層至多訪問兩個結點，極大優化了效率，

基本實作

線段樹結點

根據定義，我們可以得出線段樹結點的結構：

template <typename T, int Lim>
class SegmentTree 
{
public:
    // ...
private:
    struct Node 
    {
        T Sum;
    } Tree[Lim];
    int Size;
	// ...
};

Node結構體就是線段樹的結點，其中的Sum是該結點維護的區間和，

單點修改

線段樹的基本操作就是單點修改，根據分治思想，我們訪問結點時，如果已經到了要修改的結點（區間長度為1且已經到達目標位置），就將其值修改，否則，向它的子結點遞回，在回溯時隨便更新自己結點的值，

首先看一個pushup函式，用于更新當前結點的值，

void pushup(int root) { // 更新區間和
    Tree[root].Sum = Tree[root << 1].Sum + Tree[root << 1 | 1].Sum; 
}

這個函式把子結點的值累加到當前結點上，由于使用了陣列，子結點可以不用進行特判是否存在，直接累加即可，

遞回程序中，區間會不斷縮小，最后長度會變為$1$，即為一個點，如果這個點和要修改的點重合，就可以修改了，時間復雜度為$O(log_{2}n)$，

void modify(int root, int left, int right, int pos, T key){
	if(right < pos || left > pos) // 與當前區間無交集，回傳
		return;
	if(left == right && left == pos){ // 區間變為點且與查詢位置重合，直接修改
		Tree[left] += key;
		return;
	}
	int mid = left + right >> 1;
	modify(root << 1, left, mid, pos, key);
	modify(root << 1 | 1, mid + 1, right, pos, key);
	pushup(root); // 更新區間和
}

構建

現在有了單點修改，但對于一個初始好的序列，單點修改顯然不太方便，并且時間復雜度會過大~~（然而有時還是可以過）~~，所以我們也有一種方法快速構建線段樹，并用一個序列初始化，

void build(int root, int left, int right, T arr[]) {
    if (left == right) { // 區間變為點，保存值
        Tree[root].Sum = arr[left];
        return;
    }
    int mid = left + right >> 1;
    build(root << 1, left, mid, arr);
    build(root << 1 | 1, mid + 1, right, arr);
    pushup(root); // 更新區間和
}

單點查詢

只要在遞回是進行區間的判斷，如果查詢的位置$pos \leq mid$，則向左子樹遞回，否則向右子樹遞回，

T query(int root, int left, int right, int pos) {
    if(left == right && left == pos) { // 區間變為點且與查詢位置重合，直接回傳
        return Tree[root].Sum;
    }
    int mid = left + right >> 1;
    if(pos <= mid) return query(root << 1, left, mid, pos); // 在左邊
    else return query(root << 1 | 1, mid + 1, right, pos); // 在右邊
}

擴展實作

區間修改

如果使用單點修改來實作區間修改，時間復雜度就會達到$O((right-left+1)nlog_{2}n)$，所以，我們需要引入懶標記，在結點上加上懶標記就可以快速修改區間，

舉個例子：

迭代區間$[1,8]$，單點修改每個結點，
在區間$[1,8]$的結點上加上$v$，修改區間$[1,8]$，

很顯然，第二種效率更高，這就是懶標記，

懶標記可以是加的標記，也可以是乘的標記，只要滿足分配律，就可以使用懶標記，但是如果是開根號等等的操作就不可以，因為$\sqrt{a+b} \neq \sqrt{a} + \sqrt{b}$，

對于目前的線段樹，我們需要修改結點的結構體：

template <typename T, int Lim>
class SegmentTree 
{
public:
    // ...
private:
    struct Node 
    {
        T Add, Sum;
    } Tree[Lim];
    int Size;
	// ...
};

修改可以分為這幾個情況：

如果修改區間完全覆寫當前區間，就在當前區間的懶標記上加上值，并計算出區間和，然后回傳，
如果修改區間左端點在當前區間中點的左邊，則遞回修改左區間，
右邊類似，

然后更新當前結點，

但這里有一個問題，如果我們修改時經過一個已經打過懶標記的結點，就無法正確更新區間和，這時候就需要標記下傳了，在修改區間之前，首先標記下傳，使子結點的區間和也更新，這樣就能得到正確答案了，

void update(int root, int left, int right, T key) { // 添加懶標記
    Tree[root].Add += key; // 把懶標記加上key
    Tree[root].Sum += key * (right - left + 1); // 更新區間和
}

void pushdown(int root, int left, int right) {
    if (Tree[root].Add == 0)
        return;
    int mid = left + right >> 1;
    update(root << 1, left, mid, Tree[root].Add); // 下傳標記到左右子結點
    update(root << 1 | 1, mid + 1, right, Tree[root].Add);
    Tree[root].Add = 0; // 清楚懶標記
}

void modify(int root, int left, int right, int mleft, int mright, T key) {
    if (mleft <= left && right <= mright) { // 完全覆寫當前區間
        update(root, left, right, key); // 直接添加懶標記
        return;
    }
    int mid = left + right >> 1;
    pushdown(root, left, right);
    if (mleft <= mid) // 如果修改區間被左邊包含，則往左邊區間遞回
        modify(root << 1, left, mid, mleft, mright, key);
    if (mid < mright) // 如果修改區間被右邊包含，則往右邊區間遞回
        modify(root << 1 | 1, mid + 1, right, mleft, mright, key);
    pushup(root); // 更新
}

區間查詢

與區間查詢類似，也需要進行標記下傳，

查詢可以也可以分為這三個情況：

如果查詢區間完全覆寫當前區間，直接回傳區間和，
如果修改區間左端點在當前區間中點的左邊，則遞回查詢左區間和，
右邊類似，

最后累加左右子樹區間和，

T query(int root, int left, int right, int qleft, int qright) {
    if (qleft <= left && right <= qright)
        return Tree[root].Sum;
    int mid = left + right >> 1;
    pushdown(root, left, right);
    T res = 0;
    if (qleft <= mid)
        res += query(root << 1, left, mid, qleft, qright);
    if (mid < qright)
        res += query(root << 1 | 1, mid + 1, right, qleft, qright);
    return res;
}

完整實作

void build(T arr[]) { build(1, 1, Size, arr); }

void modify(int left, int right, T key) { modify(1, 1, Size, left, right, key); }

T query(int left, int right) { return query(1, 1, Size, left, right); }

private:
struct Node
{
T Add, Sum;
} Tree[Lim];
int Size;

void pushup(int root) { Tree[root].Sum = Tree[root << 1].Sum + Tree[root << 1 | 1].Sum; }

void update(int root, int left, int right, T key) {
    Tree[root].Add += key;
    Tree[root].Sum += key * (right - left + 1);
}

void pushdown(int root, int left, int right) {
    if (Tree[root].Add == 0)
        return;
    int mid = left + right >> 1;
    update(root << 1, left, mid, Tree[root].Add);
    update(root << 1 | 1, mid + 1, right, Tree[root].Add);
    Tree[root].Add = 0;
}

void build(int root, int left, int right, T arr[]) {
    if (left == right) {
        Tree[root].Sum = arr[left];
        return;
    }
    int mid = left + right >> 1;
    build(root << 1, left, mid, arr);
    build(root << 1 | 1, mid + 1, right, arr);
    pushup(root);
}

void modify(int root, int left, int right, int mleft, int mright, T key) {
    if (mleft <= left && right <= mright) {
        update(root, left, right, key);
        return;
    }
    int mid = left + right >> 1;
    pushdown(root, left, right);
    if (mleft <= mid)
        modify(root << 1, left, mid, mleft, mright, key);
    if (mid > mright)
        modify(root << 1 | 1, mid + 1, right, mleft, mright, key);
    pushup(root);
}

T query(int root, int left, int right, int qleft, int qright) {
    if (qleft <= left && right <= qright)
        return Tree[root].Sum;
    int mid = left + right >> 1;
    pushdown(root, left, right);
    T res = 0;
    if (qleft <= mid)
        res += query(root << 1, left, mid, qleft, qright);
    if (mid< qright)
        res += query(root << 1 | 1, mid + 1, right, qleft, qright);
    return res;
}

};

<div id="copyright">
Copyright ? 2019 ctjcalc，轉載請注明URL，并給出原文鏈接，謝謝，
</div>

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137727.html

標籤：其他

上一篇：【題解】游戲

下一篇：靠這些秋招秘笈，齊姐的學妹今年已經拿到了 8 個offer！

【資料結構】線段樹詳解