日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C++?線段樹原理與實現示例詳解_C 語言

作者：白龍碼 ? 更新時間： 2022-11-07 編程語言

一、問題引入

對于一般的區間問題，比如RMQ(區間的最值)、區間的和，如果使用樸素算法，即通過遍歷的方式求取，則時間復雜度為O(N)，在常數次查詢的情況下可以接受，但是當區間長度為N，查詢次數為M時，查詢復雜度就變成O(M*N)。在M和N較大時，這樣的復雜度無法滿足要求。

對于這類問題，有一個神奇的數據結構，能夠在O(M*logN)的時間內解決問題——線段樹。

二、線段樹的構建

線段樹的每個節點可以根據需要存儲一個區間的最大/最小值/和等內容。它的構建方式與堆的構建方式類似，即線段樹是基于數組實現的樹。

以構建區間和的線段樹為例：對于給定數組nums，設大小為n，則區間范圍為[0, n-1]。

  • 規定線段樹的根節點，即SegmentTree[0]存儲[0, n)的和。
  • 根據堆的構建方法，父節點的左孩子為2*parent+1，右孩子為2*parent+2。
  • 假設父節點存儲[start, end]的和，mid=start+(end - start>>1)，則左孩子存儲[start, mid]的和，右孩子存儲[mid+1, end]的和
  • 注：mid=start+(end - start>>1)是一種避免整形溢出的寫法，等價于mid=(start+end)/2。
  • 由于父節點的值依賴于兩個子節點，因此線段樹的構建是一種后序遍歷。
// nums是給定大小為n的數組，par表示當前正在構建的線段樹節點下標，start和end是當前需要計算的區間。
void build(vector<int>& nums, int par, int start, int end)
{
    if (start == end) // 區間大小為1，即單個點，因此當前節點的區間和就是單點的值
    {
        _segmentTree[par] = nums[start];
        return;
    }
    // 如果區間大于1，則先求當前節點的左孩子和右孩子
    int mid = start + (end - start >> 1);
    int lchild = 2 * par + 1;
    int rchild = 2 * par + 2;
    build(nums, lchild, start, mid);   // 遞歸求左節點的區間和
    build(nums, rchild, mid + 1, end); // 遞歸求右孩子的區間和
    // 當前節點的值就是左孩子的值+右孩子的值
    _segmentTree[par] = _segmentTree[lchild] + _segmentTree[rchild];
}

注：在極端情況下，最后一層有n個結點，此時線段樹是一棵完全二叉樹，樹的高度h=log2N向上取整+1≤log2N+2。

因此，樹的節點數量為2^h-1^≤2^logN+2^-1=4N-1。

所以，線段樹數組的大小一般為4*n。

此外，如果想要避免因為n過大而導致MLE，則可以選擇map/unordered_map來存儲線段樹，不過這會增加時間成本。一般來說直接開辟4*n的線段樹數組是最方便書寫的。

三、線段樹的單點修改與查詢

1、修改

單點修改要求：修改原數組下標index處的值。此時我們需要對線段樹進行更新：

  • 依然是從根節點開始進行修改。
  • 根據修改的下標index，判斷應當修改當前節點的左子樹還是右子樹。
  • 在遞歸修改左右孩子節點以后，再根據左右孩子的值重新對父節點進行賦值(pushUp())。
void update(int index, int val, int par, int start, int end)
{
    if (start == end) // 遞歸結束條件依然是當前區間為單點
    {
        segtree[par] = val;
        return;
    }
    int mid = start + (end - start >> 1);
    // 遞歸修改左孩子或右孩子
    if (index <= mid)
        update(index, val, 2 * par + 1, start, mid);
    else
        update(index, val, 2 * par + 2, mid + 1, end);
    // 修改完成后重新對父節點賦值
    pushUp(par);
}
// pushUp負責利用左右孩子的值更新父節點
void pushUp(int par)
{
    segtree[par] = segtree[2 * par + 1] + segtree[2 * par + 2];
}

2、查詢

由于每個節點可以存儲最值和區間和，因此求最值與求和的過程幾乎相同，這里以求和為例：

假設當前節點的區間為[start, end]，中點為mid。

對于給定區間[left, right]，它有三種分布情況：

  • right<=mid，即給定區間全部在左節點中，因此只需要遞歸左子樹計算區間和即可。
  • left>mid，即給定區間全部在右節點中，因此只需要遞歸右子樹計算區間和即可。
  • 給定區間有一部分在左子樹，一部分在右子樹，因此需要分成兩部分，一部分是[left, mid]，這部分到左子樹中遞歸求取。另一部分是[mid+1,right]，這部分到右子樹中遞歸求取。
// [left, right]是目標求和區間，par是當前節點編號，當前節點存儲區間[start, end]的和
int query(int left, int right, int par, int start, int end)
{
    // 目標求和區間與當前節點的區間吻合，直接返回當前節點的值即可
    if (left == start && right == end)
        return segtree[par];
    int mid = start + (end - start >> 1);
    if (right <= mid) // 目標求和區間全部在左子樹
        return query(left, right, 2 * par + 1, start, mid);
    else if (left > mid) // 目標求和區間全部在右子樹
        return query(left, right, 2 * par + 2, mid + 1, end);
    else  // 目標求和區間分布在左右子樹上
        return query(left, mid, 2 * par + 1, start, mid) +
               query(mid + 1, right, 2 * par + 2, mid + 1, end);
}

四、線段樹的區間修改與查詢

1、修改

區間修改要求：修改原數組[left, right]處的值，將它們全部加/減value，或者全部改為value。此時我們需要對線段樹進行更新。

我們可以選擇將[left, right]看成一個個點，然后進行單點修改，但是一個點的修改消耗為log2N，修改整個區間就是C*log2N了，M次修改就是M*C*log2N，這比暴力法的M*C還要差。

我們使用懶標記法，引入一個lazy變量：

依然從根節點開始修改。

如果節點對應的區間[start, end]完全包含在[left, right]中時，即left≤start≤end≤right，此時將這個節點的值進行修改，并按要求修改lazy，比如：對給定區間整體加4，則lazy加4，整體減3，則lazy減3。

修改完lazy數組后，我們不再需要修改它的子節點，因此lazy的意義在于減少向下更新的次數，從而降低時間復雜度**「懶的體現」**。

如果節點對應的區間[start, end]不完全包含在[left, right]中時，則遞歸修改左右節點，直至對應節點的區間與待修改的區間沒有交集**「遞歸的結束條件」**。子樹修改完成后，再利用子節點的值更新父節點(pushUp())。

注意：由于lazy變量的存在，使用子節點的值更新父節點時，需要加上父節點的lazy值，因為該值是由于"偷懶"而沒有添加在子節點上的。

// 以「將給定區間內的數加x，查詢每個節點存儲對應區間的和」為例：
void update(int left, int right, int x, int node, int start, int end)
{
    // 區間沒有交集，無需修改
    if (end < left || right < start)
        return;
    // 當前節點對應的區間被需要修改的區間完全包含
    if (left <= start && right >= end)
    {
        segtree[node].val += x * (end - start + 1);
        segtree[node].lazy += x;
        return;
    }
    // 不被[left, right]完全包含，則說明本輪只會更新[start, end]的一部分，因此不能再"偷懶"直接將x加在lazy上了
    // 而是先根據lazy的值修改左右子節點，然后再遞歸修改左右子樹
    int mid = start + ((end - start) >> 1);
    // 先利用lazy修改孩子節點
    pushDown(node, mid - start + 1, end - mid);
    // 遞歸修改孩子節點
    update(left, right, 2 * node + 1, start, mid);
    update(left, right, 2 * node + 2, mid + 1, end);
    // 利用左右子樹的區間最大值確定父節點的區間最大值
    pushUp(par);
}
void pushUp(int par)
{
	segtree[par].val = segtree[2 * par + 1] + segtree[2 * par + 2] + segtree[par].lazy;
}
// par表示父節點，ln表示左孩子的區間長度，rn表示右孩子的區間長度
void pushDown(int par, int ln, int rn)
{
    if (segtree[par].lazy != 0)
    {
        segtree[2 * par + 1].val += segtree[par].lazy * ln; // 修改左孩子的值
        segtree[2 * par + 1].lazy += segtree[par].lazy; // 偷懶，不再往下繼續修改，因此左孩子繼承父節點的lazy值
        segtree[2 * par + 2].lazy += segtree[par].lazy * rn;
        segtree[2 * par + 2].lazy += segtree[par].lazy;
        segtree[par].lazy = 0; // 父節點的lazy已經分配到子節點了，因此父節點lazy清零
    }
}

2、查詢

查詢的過程與修改幾乎相同：

  • 依然從根節點開始查詢。
  • 如果當前節點有懶標記，此時返回節點的值，無需向下遍歷。
  • 當某個節點對應的區間[start, end]完全包含在[left, right]中時，即left≤start≤end≤right，則該節點的值是我們最終結果的子集，直接返回節點值即可。
  • 如果不完全包含，則遞歸查詢左右子樹，直至對應節點的區間與待修改的區間沒有交集**「遞歸的結束條件」**。利用子樹的查詢結果作為最終的返回結果。
// 以「將給定區間內的數加x，查詢每個節點存儲對應區間的和」為例：
bool query(int left, int right, int node, int start, int end)
{
    // 區間沒有交集，無需查詢
    if (end < left || right < start)
        return false;
    // 有懶標記，則無需查詢左右孩子，而是直接返回節點值，外加懶標記
    // 或者當前節點對應的區間被需要查詢的區間完全包含，則直接返回節點值
    if (segtree[node].lazy || left <= start && right >= end)
        return segtree[node].val;
    int mid = start + ((end - start) >> 1);
    // 不完全包含，則先根據lazy修改子節點，再遞歸查詢左右子樹的和
    pushDown(node, mid - start + 1, end - mid);  
    return query(left, right, 2 * node + 1, start, mid) +
           query(left, right, 2 * node + 2, mid + 1, end);
}
// par表示父節點，ln表示左孩子的區間長度，rn表示右孩子的區間長度
void pushDown(int par, int ln, int rn)
{
    if (segtree[par].lazy != 0)
    {
        segtree[2 * par + 1].val += segtree[par].lazy * ln; // 修改左孩子的值
        segtree[2 * par + 1].lazy += segtree[par].lazy; // 偷懶，不再往下繼續修改，因此左孩子繼承父節點的lazy值
        segtree[2 * par + 2].lazy += segtree[par].lazy * rn;
        segtree[2 * par + 2].lazy += segtree[par].lazy;
        segtree[par].lazy = 0; // 父節點的lazy已經分配到子節點了，因此父節點lazy清零
    }
}

原文鏈接：https://juejin.cn/post/7143218626990964766

欄目分類
最近更新