C++?線段樹原理與實(shí)現(xiàn)示例詳解
一、問題引入
對(duì)于一般的區(qū)間問題，比如RMQ(區(qū)間的最值)、區(qū)間的和，如果使用樸素算法，即通過(guò)遍歷的方式求取，則時(shí)間復(fù)雜度為O(N)，在常數(shù)次查詢的情況下可以接受，但是當(dāng)區(qū)間長(zhǎng)度為N，查詢次數(shù)為M時(shí)，查詢復(fù)雜度就變成O(M*N)。在M和N較大時(shí)，這樣的復(fù)雜度無(wú)法滿足要求。
對(duì)于這類問題，有一個(gè)神奇的數(shù)據(jù)結(jié)構(gòu)，能夠在O(M*logN)的時(shí)間內(nèi)解決問題——線段樹。
二、線段樹的構(gòu)建
線段樹的每個(gè)節(jié)點(diǎn)可以根據(jù)需要存儲(chǔ)一個(gè)區(qū)間的最大/最小值/和等內(nèi)容。它的構(gòu)建方式與堆的構(gòu)建方式類似，即線段樹是基于數(shù)組實(shí)現(xiàn)的樹。
以構(gòu)建區(qū)間和的線段樹為例：對(duì)于給定數(shù)組nums，設(shè)大小為n，則區(qū)間范圍為[0, n-1]。
- 規(guī)定線段樹的根節(jié)點(diǎn)，即
SegmentTree[0]存儲(chǔ)[0, n)的和。 - 根據(jù)堆的構(gòu)建方法，父節(jié)點(diǎn)的左孩子為2*parent+1，右孩子為2*parent+2。
- 假設(shè)父節(jié)點(diǎn)存儲(chǔ)[start, end]的和，
mid=start+(end - start>>1)，則左孩子存儲(chǔ)[start, mid]的和，右孩子存儲(chǔ)[mid+1, end]的和 - 注：
mid=start+(end - start>>1)是一種避免整形溢出的寫法，等價(jià)于mid=(start+end)/2。 - 由于父節(jié)點(diǎn)的值依賴于兩個(gè)子節(jié)點(diǎn)，因此線段樹的構(gòu)建是一種后序遍歷。
// nums是給定大小為n的數(shù)組，par表示當(dāng)前正在構(gòu)建的線段樹節(jié)點(diǎn)下標(biāo)，start和end是當(dāng)前需要計(jì)算的區(qū)間。
void build(vector<int>& nums, int par, int start, int end)
{
if (start == end) // 區(qū)間大小為1，即單個(gè)點(diǎn)，因此當(dāng)前節(jié)點(diǎn)的區(qū)間和就是單點(diǎn)的值
{
_segmentTree[par] = nums[start];
return;
}
// 如果區(qū)間大于1，則先求當(dāng)前節(jié)點(diǎn)的左孩子和右孩子
int mid = start + (end - start >> 1);
int lchild = 2 * par + 1;
int rchild = 2 * par + 2;
build(nums, lchild, start, mid); // 遞歸求左節(jié)點(diǎn)的區(qū)間和
build(nums, rchild, mid + 1, end); // 遞歸求右孩子的區(qū)間和
// 當(dāng)前節(jié)點(diǎn)的值就是左孩子的值+右孩子的值
_segmentTree[par] = _segmentTree[lchild] + _segmentTree[rchild];
}
注：在極端情況下，最后一層有n個(gè)結(jié)點(diǎn)，此時(shí)線段樹是一棵完全二叉樹，樹的高度h=log2N向上取整+1≤log2N+2。
因此，樹的節(jié)點(diǎn)數(shù)量為2^h-1^≤2^logN+2^-1=4N-1。
所以，線段樹數(shù)組的大小一般為4*n。
此外，如果想要避免因?yàn)閚過(guò)大而導(dǎo)致MLE，則可以選擇map/unordered_map來(lái)存儲(chǔ)線段樹，不過(guò)這會(huì)增加時(shí)間成本。一般來(lái)說(shuō)直接開辟4*n的線段樹數(shù)組是最方便書寫的。
三、線段樹的單點(diǎn)修改與查詢
1、修改
單點(diǎn)修改要求：修改原數(shù)組下標(biāo)index處的值。此時(shí)我們需要對(duì)線段樹進(jìn)行更新：
- 依然是從根節(jié)點(diǎn)開始進(jìn)行修改。
- 根據(jù)修改的下標(biāo)index，判斷應(yīng)當(dāng)修改當(dāng)前節(jié)點(diǎn)的左子樹還是右子樹。
- 在遞歸修改左右孩子節(jié)點(diǎn)以后，再根據(jù)左右孩子的值重新對(duì)父節(jié)點(diǎn)進(jìn)行賦值(
pushUp())。
void update(int index, int val, int par, int start, int end)
{
if (start == end) // 遞歸結(jié)束條件依然是當(dāng)前區(qū)間為單點(diǎn)
{
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);
// 修改完成后重新對(duì)父節(jié)點(diǎn)賦值
pushUp(par);
}
// pushUp負(fù)責(zé)利用左右孩子的值更新父節(jié)點(diǎn)
void pushUp(int par)
{
segtree[par] = segtree[2 * par + 1] + segtree[2 * par + 2];
}
2、查詢
由于每個(gè)節(jié)點(diǎn)可以存儲(chǔ)最值和區(qū)間和，因此求最值與求和的過(guò)程幾乎相同，這里以求和為例：
假設(shè)當(dāng)前節(jié)點(diǎn)的區(qū)間為[start, end]，中點(diǎn)為mid。
對(duì)于給定區(qū)間[left, right]，它有三種分布情況：
- right<=mid，即給定區(qū)間全部在左節(jié)點(diǎn)中，因此只需要遞歸左子樹計(jì)算區(qū)間和即可。
- left>mid，即給定區(qū)間全部在右節(jié)點(diǎn)中，因此只需要遞歸右子樹計(jì)算區(qū)間和即可。
- 給定區(qū)間有一部分在左子樹，一部分在右子樹，因此需要分成兩部分，一部分是[left, mid]，這部分到左子樹中遞歸求取。另一部分是[mid+1,right]，這部分到右子樹中遞歸求取。
// [left, right]是目標(biāo)求和區(qū)間，par是當(dāng)前節(jié)點(diǎn)編號(hào)，當(dāng)前節(jié)點(diǎn)存儲(chǔ)區(qū)間[start, end]的和
int query(int left, int right, int par, int start, int end)
{
// 目標(biāo)求和區(qū)間與當(dāng)前節(jié)點(diǎn)的區(qū)間吻合，直接返回當(dāng)前節(jié)點(diǎn)的值即可
if (left == start && right == end)
return segtree[par];
int mid = start + (end - start >> 1);
if (right <= mid) // 目標(biāo)求和區(qū)間全部在左子樹
return query(left, right, 2 * par + 1, start, mid);
else if (left > mid) // 目標(biāo)求和區(qū)間全部在右子樹
return query(left, right, 2 * par + 2, mid + 1, end);
else // 目標(biāo)求和區(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]處的值，將它們?nèi)考?減value，或者全部改為value。此時(shí)我們需要對(duì)線段樹進(jìn)行更新。
我們可以選擇將[left, right]看成一個(gè)個(gè)點(diǎn)，然后進(jìn)行單點(diǎn)修改，但是一個(gè)點(diǎn)的修改消耗為log2N，修改整個(gè)區(qū)間就是C*log2N了，M次修改就是M*C*log2N，這比暴力法的M*C還要差。
我們使用懶標(biāo)記法，引入一個(gè)lazy變量：
依然從根節(jié)點(diǎn)開始修改。
如果節(jié)點(diǎn)對(duì)應(yīng)的區(qū)間[start, end]完全包含在[left, right]中時(shí)，即left≤start≤end≤right，此時(shí)將這個(gè)節(jié)點(diǎn)的值進(jìn)行修改，并按要求修改lazy，比如：對(duì)給定區(qū)間整體加4，則lazy加4，整體減3，則lazy減3。
修改完lazy數(shù)組后，我們不再需要修改它的子節(jié)點(diǎn)，因此lazy的意義在于減少向下更新的次數(shù)，從而降低時(shí)間復(fù)雜度**「懶的體現(xiàn)」**。
如果節(jié)點(diǎn)對(duì)應(yīng)的區(qū)間[start, end]不完全包含在[left, right]中時(shí)，則遞歸修改左右節(jié)點(diǎn)，直至對(duì)應(yīng)節(jié)點(diǎn)的區(qū)間與待修改的區(qū)間沒有交集**「遞歸的結(jié)束條件」**。子樹修改完成后，再利用子節(jié)點(diǎn)的值更新父節(jié)點(diǎn)(pushUp())。
注意：由于lazy變量的存在，使用子節(jié)點(diǎn)的值更新父節(jié)點(diǎn)時(shí)，需要加上父節(jié)點(diǎn)的lazy值，因?yàn)樵撝凳怯捎?quot;偷懶"而沒有添加在子節(jié)點(diǎn)上的。
// 以「將給定區(qū)間內(nèi)的數(shù)加x，查詢每個(gè)節(jié)點(diǎn)存儲(chǔ)對(duì)應(yīng)區(qū)間的和」為例：
void update(int left, int right, int x, int node, int start, int end)
{
// 區(qū)間沒有交集，無(wú)需修改
if (end < left || right < start)
return;
// 當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的區(qū)間被需要修改的區(qū)間完全包含
if (left <= start && right >= end)
{
segtree[node].val += x * (end - start + 1);
segtree[node].lazy += x;
return;
}
// 不被[left, right]完全包含，則說(shuō)明本輪只會(huì)更新[start, end]的一部分，因此不能再"偷懶"直接將x加在lazy上了
// 而是先根據(jù)lazy的值修改左右子節(jié)點(diǎn)，然后再遞歸修改左右子樹
int mid = start + ((end - start) >> 1);
// 先利用lazy修改孩子節(jié)點(diǎn)
pushDown(node, mid - start + 1, end - mid);
// 遞歸修改孩子節(jié)點(diǎn)
update(left, right, 2 * node + 1, start, mid);
update(left, right, 2 * node + 2, mid + 1, end);
// 利用左右子樹的區(qū)間最大值確定父節(jié)點(diǎn)的區(qū)間最大值
pushUp(par);
}
void pushUp(int par)
{
segtree[par].val = segtree[2 * par + 1] + segtree[2 * par + 2] + segtree[par].lazy;
}
// par表示父節(jié)點(diǎn)，ln表示左孩子的區(qū)間長(zhǎng)度，rn表示右孩子的區(qū)間長(zhǎng)度
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é)點(diǎn)的lazy值
segtree[2 * par + 2].lazy += segtree[par].lazy * rn;
segtree[2 * par + 2].lazy += segtree[par].lazy;
segtree[par].lazy = 0; // 父節(jié)點(diǎn)的lazy已經(jīng)分配到子節(jié)點(diǎn)了，因此父節(jié)點(diǎn)lazy清零
}
}
2、查詢
查詢的過(guò)程與修改幾乎相同：
- 依然從根節(jié)點(diǎn)開始查詢。
- 如果當(dāng)前節(jié)點(diǎn)有懶標(biāo)記，此時(shí)返回節(jié)點(diǎn)的值，無(wú)需向下遍歷。
- 當(dāng)某個(gè)節(jié)點(diǎn)對(duì)應(yīng)的區(qū)間[start, end]完全包含在[left, right]中時(shí)，即
left≤start≤end≤right，則該節(jié)點(diǎn)的值是我們最終結(jié)果的子集，直接返回節(jié)點(diǎn)值即可。 - 如果不完全包含，則遞歸查詢左右子樹，直至對(duì)應(yīng)節(jié)點(diǎn)的區(qū)間與待修改的區(qū)間沒有交集**「遞歸的結(jié)束條件」**。利用子樹的查詢結(jié)果作為最終的返回結(jié)果。
// 以「將給定區(qū)間內(nèi)的數(shù)加x，查詢每個(gè)節(jié)點(diǎn)存儲(chǔ)對(duì)應(yīng)區(qū)間的和」為例：
bool query(int left, int right, int node, int start, int end)
{
// 區(qū)間沒有交集，無(wú)需查詢
if (end < left || right < start)
return false;
// 有懶標(biāo)記，則無(wú)需查詢左右孩子，而是直接返回節(jié)點(diǎn)值，外加懶標(biāo)記
// 或者當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的區(qū)間被需要查詢的區(qū)間完全包含，則直接返回節(jié)點(diǎn)值
if (segtree[node].lazy || left <= start && right >= end)
return segtree[node].val;
int mid = start + ((end - start) >> 1);
// 不完全包含，則先根據(jù)lazy修改子節(jié)點(diǎn)，再遞歸查詢左右子樹的和
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é)點(diǎn)，ln表示左孩子的區(qū)間長(zhǎng)度，rn表示右孩子的區(qū)間長(zhǎng)度
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é)點(diǎn)的lazy值
segtree[2 * par + 2].lazy += segtree[par].lazy * rn;
segtree[2 * par + 2].lazy += segtree[par].lazy;
segtree[par].lazy = 0; // 父節(jié)點(diǎn)的lazy已經(jīng)分配到子節(jié)點(diǎn)了，因此父節(jié)點(diǎn)lazy清零
}
}
以上就是C++ 線段樹原理與實(shí)現(xiàn)示例詳解的詳細(xì)內(nèi)容，更多關(guān)于C++ 線段樹原理的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
IOS 開發(fā)UITextView回收或關(guān)閉鍵盤
這篇文章主要介紹了IOS 開發(fā)UITextView回收或關(guān)閉鍵盤的相關(guān)資料,需要的朋友可以參考下2017-06-06
C語(yǔ)言實(shí)現(xiàn)掃雷小游戲詳細(xì)代碼
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)掃雷小游戲的代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06
解析Linux下的時(shí)間函數(shù):設(shè)置以及獲取時(shí)間的方法
本篇文章是對(duì)Linux下的時(shí)間函數(shù):設(shè)置以及獲取時(shí)間的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言編寫簡(jiǎn)單拼圖游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
本文主要介紹了C++中map容器的具體使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
Protocol Buffer技術(shù)深入理解(C++實(shí)例)
C++實(shí)例Protocol Buffer技術(shù)詳解,感興趣的朋友可以了解下2013-01-01
這篇文章主要為大家詳細(xì)介紹了C++中的函數(shù)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-02-02
C++哈希應(yīng)用之位圖,哈希切分與布隆過(guò)濾器詳解
這篇文章主要為大家詳細(xì)介紹了C++哈希應(yīng)用中的位圖、哈希切分與布隆過(guò)濾器，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價(jià)值，需要的可以參考一下2023-04-04
Lambda表達(dá)式是現(xiàn)代C++在C ++ 11和更高版本中的一個(gè)新的語(yǔ)法糖 ,在C++11、C++14、C++17和C++20中Lambda表達(dá)的內(nèi)容還在不斷更新。 lambda表達(dá)式(也稱為lambda函數(shù))是在調(diào)用或作為函數(shù)參數(shù)傳遞的位置處定義匿名函數(shù)對(duì)象的便捷方法2022-05-05
C++實(shí)現(xiàn)帶頭雙向循環(huán)鏈表的示例詳解
這篇文章主要介紹了如何利用C++實(shí)現(xiàn)帶頭雙向循環(huán)鏈表，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-12-12