C++?線段樹原理與實現(xiàn)示例詳解
一、問題引入
對于一般的區(qū)間問題，比如RMQ(區(qū)間的最值)、區(qū)間的和，如果使用樸素算法，即通過遍歷的方式求取，則時間復雜度為O(N)，在常數(shù)次查詢的情況下可以接受，但是當區(qū)間長度為N，查詢次數(shù)為M時，查詢復雜度就變成O(M*N)。在M和N較大時，這樣的復雜度無法滿足要求。
對于這類問題，有一個神奇的數(shù)據(jù)結構，能夠在O(M*logN)的時間內解決問題——線段樹。
二、線段樹的構建
線段樹的每個節(jié)點可以根據(jù)需要存儲一個區(qū)間的最大/最小值/和等內容。它的構建方式與堆的構建方式類似，即線段樹是基于數(shù)組實現(xiàn)的樹。
以構建區(qū)間和的線段樹為例：對于給定數(shù)組nums，設大小為n，則區(qū)間范圍為[0, n-1]。
- 規(guī)定線段樹的根節(jié)點，即
SegmentTree[0]存儲[0, n)的和。 - 根據(jù)堆的構建方法，父節(jié)點的左孩子為2*parent+1，右孩子為2*parent+2。
- 假設父節(jié)點存儲[start, end]的和，
mid=start+(end - start>>1)，則左孩子存儲[start, mid]的和，右孩子存儲[mid+1, end]的和 - 注：
mid=start+(end - start>>1)是一種避免整形溢出的寫法，等價于mid=(start+end)/2。 - 由于父節(jié)點的值依賴于兩個子節(jié)點，因此線段樹的構建是一種后序遍歷。
// nums是給定大小為n的數(shù)組，par表示當前正在構建的線段樹節(jié)點下標，start和end是當前需要計算的區(qū)間。
void build(vector<int>& nums, int par, int start, int end)
{
if (start == end) // 區(qū)間大小為1，即單個點，因此當前節(jié)點的區(qū)間和就是單點的值
{
_segmentTree[par] = nums[start];
return;
}
// 如果區(qū)間大于1，則先求當前節(jié)點的左孩子和右孩子
int mid = start + (end - start >> 1);
int lchild = 2 * par + 1;
int rchild = 2 * par + 2;
build(nums, lchild, start, mid); // 遞歸求左節(jié)點的區(qū)間和
build(nums, rchild, mid + 1, end); // 遞歸求右孩子的區(qū)間和
// 當前節(jié)點的值就是左孩子的值+右孩子的值
_segmentTree[par] = _segmentTree[lchild] + _segmentTree[rchild];
}
注：在極端情況下，最后一層有n個結點，此時線段樹是一棵完全二叉樹，樹的高度h=log2N向上取整+1≤log2N+2。
因此，樹的節(jié)點數(shù)量為2^h-1^≤2^logN+2^-1=4N-1。
所以，線段樹數(shù)組的大小一般為4*n。
此外，如果想要避免因為n過大而導致MLE，則可以選擇map/unordered_map來存儲線段樹，不過這會增加時間成本。一般來說直接開辟4*n的線段樹數(shù)組是最方便書寫的。
三、線段樹的單點修改與查詢
1、修改
單點修改要求：修改原數(shù)組下標index處的值。此時我們需要對線段樹進行更新：
- 依然是從根節(jié)點開始進行修改。
- 根據(jù)修改的下標index，判斷應當修改當前節(jié)點的左子樹還是右子樹。
- 在遞歸修改左右孩子節(jié)點以后，再根據(jù)左右孩子的值重新對父節(jié)點進行賦值(
pushUp())。
void update(int index, int val, int par, int start, int end)
{
if (start == end) // 遞歸結束條件依然是當前區(qū)間為單點
{
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);
// 修改完成后重新對父節(jié)點賦值
pushUp(par);
}
// pushUp負責利用左右孩子的值更新父節(jié)點
void pushUp(int par)
{
segtree[par] = segtree[2 * par + 1] + segtree[2 * par + 2];
}
2、查詢
由于每個節(jié)點可以存儲最值和區(qū)間和，因此求最值與求和的過程幾乎相同，這里以求和為例：
假設當前節(jié)點的區(qū)間為[start, end]，中點為mid。
對于給定區(qū)間[left, right]，它有三種分布情況：
- right<=mid，即給定區(qū)間全部在左節(jié)點中，因此只需要遞歸左子樹計算區(qū)間和即可。
- left>mid，即給定區(qū)間全部在右節(jié)點中，因此只需要遞歸右子樹計算區(qū)間和即可。
- 給定區(qū)間有一部分在左子樹，一部分在右子樹，因此需要分成兩部分，一部分是[left, mid]，這部分到左子樹中遞歸求取。另一部分是[mid+1,right]，這部分到右子樹中遞歸求取。
// [left, right]是目標求和區(qū)間，par是當前節(jié)點編號，當前節(jié)點存儲區(qū)間[start, end]的和
int query(int left, int right, int par, int start, int end)
{
// 目標求和區(qū)間與當前節(jié)點的區(qū)間吻合，直接返回當前節(jié)點的值即可
if (left == start && right == end)
return segtree[par];
int mid = start + (end - start >> 1);
if (right <= mid) // 目標求和區(qū)間全部在左子樹
return query(left, right, 2 * par + 1, start, mid);
else if (left > mid) // 目標求和區(qū)間全部在右子樹
return query(left, right, 2 * par + 2, mid + 1, end);
else // 目標求和區(qū)間分布在左右子樹上
return query(left, mid, 2 * par + 1, start, mid) +
query(mid + 1, right, 2 * par + 2, mid + 1, end);
}
四、線段樹的區(qū)間修改與查詢
1、修改
區(qū)間修改要求：修改原數(shù)組[left, right]處的值，將它們全部加/減value，或者全部改為value。此時我們需要對線段樹進行更新。
我們可以選擇將[left, right]看成一個個點，然后進行單點修改，但是一個點的修改消耗為log2N，修改整個區(qū)間就是C*log2N了，M次修改就是M*C*log2N，這比暴力法的M*C還要差。
我們使用懶標記法，引入一個lazy變量：
依然從根節(jié)點開始修改。
如果節(jié)點對應的區(qū)間[start, end]完全包含在[left, right]中時，即left≤start≤end≤right，此時將這個節(jié)點的值進行修改，并按要求修改lazy，比如：對給定區(qū)間整體加4，則lazy加4，整體減3，則lazy減3。
修改完lazy數(shù)組后，我們不再需要修改它的子節(jié)點，因此lazy的意義在于減少向下更新的次數(shù)，從而降低時間復雜度**「懶的體現(xiàn)」**。
如果節(jié)點對應的區(qū)間[start, end]不完全包含在[left, right]中時，則遞歸修改左右節(jié)點，直至對應節(jié)點的區(qū)間與待修改的區(qū)間沒有交集**「遞歸的結束條件」**。子樹修改完成后，再利用子節(jié)點的值更新父節(jié)點(pushUp())。
注意：由于lazy變量的存在，使用子節(jié)點的值更新父節(jié)點時，需要加上父節(jié)點的lazy值，因為該值是由于"偷懶"而沒有添加在子節(jié)點上的。
// 以「將給定區(qū)間內的數(shù)加x，查詢每個節(jié)點存儲對應區(qū)間的和」為例：
void update(int left, int right, int x, int node, int start, int end)
{
// 區(qū)間沒有交集，無需修改
if (end < left || right < start)
return;
// 當前節(jié)點對應的區(qū)間被需要修改的區(qū)間完全包含
if (left <= start && right >= end)
{
segtree[node].val += x * (end - start + 1);
segtree[node].lazy += x;
return;
}
// 不被[left, right]完全包含，則說明本輪只會更新[start, end]的一部分，因此不能再"偷懶"直接將x加在lazy上了
// 而是先根據(jù)lazy的值修改左右子節(jié)點，然后再遞歸修改左右子樹
int mid = start + ((end - start) >> 1);
// 先利用lazy修改孩子節(jié)點
pushDown(node, mid - start + 1, end - mid);
// 遞歸修改孩子節(jié)點
update(left, right, 2 * node + 1, start, mid);
update(left, right, 2 * node + 2, mid + 1, end);
// 利用左右子樹的區(qū)間最大值確定父節(jié)點的區(qū)間最大值
pushUp(par);
}
void pushUp(int par)
{
segtree[par].val = segtree[2 * par + 1] + segtree[2 * par + 2] + segtree[par].lazy;
}
// par表示父節(jié)點，ln表示左孩子的區(qū)間長度，rn表示右孩子的區(qū)間長度
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; // 偷懶，不再往下繼續(xù)修改，因此左孩子繼承父節(jié)點的lazy值
segtree[2 * par + 2].lazy += segtree[par].lazy * rn;
segtree[2 * par + 2].lazy += segtree[par].lazy;
segtree[par].lazy = 0; // 父節(jié)點的lazy已經(jīng)分配到子節(jié)點了，因此父節(jié)點lazy清零
}
}
2、查詢
查詢的過程與修改幾乎相同：
- 依然從根節(jié)點開始查詢。
- 如果當前節(jié)點有懶標記，此時返回節(jié)點的值，無需向下遍歷。
- 當某個節(jié)點對應的區(qū)間[start, end]完全包含在[left, right]中時，即
left≤start≤end≤right，則該節(jié)點的值是我們最終結果的子集，直接返回節(jié)點值即可。 - 如果不完全包含，則遞歸查詢左右子樹，直至對應節(jié)點的區(qū)間與待修改的區(qū)間沒有交集**「遞歸的結束條件」**。利用子樹的查詢結果作為最終的返回結果。
// 以「將給定區(qū)間內的數(shù)加x，查詢每個節(jié)點存儲對應區(qū)間的和」為例：
bool query(int left, int right, int node, int start, int end)
{
// 區(qū)間沒有交集，無需查詢
if (end < left || right < start)
return false;
// 有懶標記，則無需查詢左右孩子，而是直接返回節(jié)點值，外加懶標記
// 或者當前節(jié)點對應的區(qū)間被需要查詢的區(qū)間完全包含，則直接返回節(jié)點值
if (segtree[node].lazy || left <= start && right >= end)
return segtree[node].val;
int mid = start + ((end - start) >> 1);
// 不完全包含，則先根據(jù)lazy修改子節(jié)點，再遞歸查詢左右子樹的和
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表示父節(jié)點，ln表示左孩子的區(qū)間長度，rn表示右孩子的區(qū)間長度
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; // 偷懶，不再往下繼續(xù)修改，因此左孩子繼承父節(jié)點的lazy值
segtree[2 * par + 2].lazy += segtree[par].lazy * rn;
segtree[2 * par + 2].lazy += segtree[par].lazy;
segtree[par].lazy = 0; // 父節(jié)點的lazy已經(jīng)分配到子節(jié)點了，因此父節(jié)點lazy清零
}
}
以上就是C++ 線段樹原理與實現(xiàn)示例詳解的詳細內容，更多關于C++ 線段樹原理的資料請關注腳本之家其它相關文章！
相關文章
本文主要介紹C語言中的條件運算符,并提供示例代碼以便大家學習參考,希望能幫助學習 C語言的同學2016-07-07
使用opencv實現(xiàn)車道線檢測實戰(zhàn)代碼
這篇文章主要介紹了opencv車道線檢測實戰(zhàn),效果非常逼真，代碼簡單易懂，對opencv車道線檢測實戰(zhàn)代碼感興趣的朋友一起看看吧2022-03-03
C++實現(xiàn)字符串轉整數(shù)(atoi)的代碼詳解
在編程中,經(jīng)常會遇到將字符串轉換為整數(shù)的需求,就像標準庫中的 atoi 函數(shù)一樣,本文給大家介紹了C++中字符串轉整數(shù)（atoi）的實現(xiàn)與解析,并有詳細的代碼示例供大家參考,需要的朋友可以參考下2025-04-04
這篇文章主要介紹了北郵考研復試C語言上機題目精選,摘自2010年北郵CS的復試,需要的朋友可以參考下2015-08-08
這篇文章主要介紹了C++封裝靜態(tài)鏈接庫和使用,本文描述了怎么去把一個C++程序封裝成一個靜態(tài)庫并且如何去使用這些靜態(tài)庫，需要的朋友可以參考下2022-08-08
今天小編就為大家分享一篇關于C++11并發(fā)編程:多線程std::thread，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要介紹了C++ QT智能指針的使用,Qt是一個跨平臺的C++框架,主要用來開發(fā)圖形用戶界面程序,也可以開發(fā)不帶界面的命令行程序,下面我們來了解QT智能指針是如何使用的2023-12-12
本篇文章是對Reactor反應器的實現(xiàn)方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡易停車場管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了使用C++制作GC Server過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-09-09