一個下標從1開始，長度為10的數組構成的線段樹例子

我的建議是構造線段樹時的數組下標從1開始，在上圖中，[1 , 10]為1，[1 , 5]為2，[6 , 10]為3，以此類推，這樣子構造，若父節點的下標為X，左右子節點則分別為2*X和2*X+1，在向上遞歸時，子節點的下標直接除以2就是父節點的下標（左葉子節點均為偶數，右葉子節點均為奇數）。

二，作用及原理

線段樹的作用是進行區間快速的修改，查詢，當區間的左端點與右端點相等時，即單點的修改與查詢，也適用於線段樹。

可以發現，線段樹由於其自身性質，任意兩個沒有祖先關係的節點之間，他們所存儲的線段範圍是不會相交的。因此，這縮短了改查的時間，從 N 降低到 log（N），比如在上圖中，要查詢線段[4 , 10]的信息（可能是總值，可能是最值等等），只需要往下查詢到[4 , 5]和[6 , 10]兩個節點，遞歸時總結兩個節點的信息即可。

比如當你要將數組區間[200 , 200000]的元素全部增加或者刪除某個數或者查詢這個區間中元素的總和或者最值等等，按照暴力的方法枚舉需要十萬次級別的運算次數，在線段樹中只需要 次運算，即大約十八次運算，其中底數為2（二叉樹結構決定），

在進行線段樹的操作時，一般分為三種情況來，設需要操作的線段的左右端點分別為targ_L和targ_R，當前查詢的節點的線段端點為L和R。

• 如果[targ_L ， targ_R]和[L ， R]無交點，則直接return。即targ_L > R || targ_R < L

• 如果[targ_L ， targ_R]包含[L ， R],則返回線段數據，因為當前正查詢的線段是所求線段中的一部分。即targ_L <= L && targ_R >= R

• 其他情況，包括[targ_L ， targ_R]和[L ， R]有部分相交和[L ， R]包含[targ_L ， targ_R]的情況（比如當前查詢到第一節點）。即除上兩種情況外else。此時要分別查詢當前節點的左右子節點。

舉個例子，我們現在所求的是線段中的元素總和。

首先聲明結構體，其中：

int L, R, VAL ;分別為線段左右端點和線段中元素總和。

查詢函數：int interval_query(int targ_L, int targ_R, int L, int R, int tot)

參數為目標左端點，目標右端點，當前左端點，當前右端點，目前節點的下標

內容：

if(targ_L > R || targ_R < L)return 0;

if(targ_L <= L && targ_R >= R)return Node[tot].val; ////Node為線段樹結構體

int mid=(l + r) / 2;

int a=interval_query(targ_l, targ_r, l, mid, tot * 2);

int b=interval_query(targ_l, targ_r, mid + 1, r, tot * 2 + 1);

return a + b;

上述代碼就是區間查詢的代碼。

可以發現，當操作的區間左右端點相同，比如[4 , 4]，即單點操作，所需的操作數也是 ，N為構成線段樹數組的最大下標，這相比與暴力操作中（1次）要慢。另一種情況，使用數組前綴和來查詢區間元素和，查詢時次數為1，但是修改時的次數為N，因此，某種程度上，線段樹將查詢和修改次數統一為 ，某種意義上來說算是一種互相妥協。當然當N足夠大時， 要遠遠小於 ，因此當N比較大時，線段樹要相對快很多。

三，線段樹中最重要的----延遲標記

可以注意到，當線段樹進行暴力區間的修改時，要修改大量葉子節點的屬性，修改一次理論次數 級別，此時很慢，因此引入線段樹節點的另一個屬性，延遲標記，從而修改一次的理論次數可以降到 級別。

延遲標記相當於先打借條，還是上述[4 , 10]和區間求和的例子，若是無延遲標記的情況下，不僅需要修改[4 , 5]和[6 , 10]的值，還需要修改其父節點和子節點的值，即除了[1 , 5]的左子樹外的節點都要修改，但引進延遲標記後，[4 , 5]和[6 , 10]的父節點的信息在從根節點遞歸來的時候進行更新，到了[4 , 5]和[6 , 10]的時候，為這兩個節點打上延遲標記，代表的意思是，[4 , 5]和[6 , 10]的所有子節點，需要增加所打的延遲標記的值，這相當於打借條，當查詢的時候查詢到有延遲標記的節點時，進行本節點的更新，再將延遲標記傳給它的子節點（如果沒有子節點即L==R則return）。相當於在查詢過程中順便更新了值，不會增加多餘的操作數，如果程序全程沒有查詢到該帶有延遲標記的節點，那麼這個借條也就不兌現了。

因此，線段樹的區間修改和區間查詢的代碼中除了上述三種情況外，還需增加對延遲標記的操作，結構體中也需要加入延遲標記變數。

int lazy ;

具體操作（以求和為例）：

修改時：噹噹前所查詢的區間包圍於目標區間中時，打上延遲標記。

Node[tot] . lazy += val ;

查詢時：噹噹前節點存在延遲標記時，該節點

Node[tot * 2] . val += Node[tot] . lazy ;

Node[tot * 2 + 1] . val += Node[tot] . lazy ;

然後判斷該節點是否有子節點，即（L==R），如果有子節點，將延遲標記傳遞到子節點上

否則不管。最後將

Node[tot] . lazy = 0 ; 。

四，額外說明

需要使用線段樹的題目並不會很隱晦，常常不難看出來，但是變種比較多，所需的線段信息的不同會導致之間代碼差異較大，因此對於線段樹，需要理解透徹其中的操作，要會延遲標記的合理使用，不同於FFT或最大流等題目，有模板可套，線段樹更多還是依賴於題目的實際情況來寫代碼。

本文第五部分中的線段樹代碼沒有單點修改和單點查詢，只需調用區間的修改和查詢時左右端點設相同即為單點查詢。只有三個基本函數：

• 建樹
• 區間（單點）修改
• 區間（單點）查詢

線段樹節點大小要開到原數組的四倍，這是樹狀結構決定的（注意處理邊界情況，即判斷L是否等於R，如果等於即無子節點，否則有子節點）。

注意類變數要聲明在全局中，一般情況下，點數到十萬無法聲明局部變數。

文中代碼電腦上看比較方便。

五，具體實現

例子為區間求和和區間最（大）值。

代碼封裝於類interval_play中，類中的線段樹類為Segtree，帶有四個變數，val，l，r 和 lazy

區間求和代碼：

class interval_play{
public:
class Segtree{
public:
int val, l, r, lazy;
}Node[maxn * 4 + 100];

int ini_val[maxn]; ////構成線段樹的數組初始值
void init(int n)
{
for(int i = 1;i <= n * 4 + 100;i++)Node[i].lazy = 0; ////清空延遲標記
}
void build(int l, int r, int tot) ////當前節點的左右節點和節點下標
{
Node[tot].l = l; Node[tot].r = r;
if(l == r)
{
Node[tot].val = ini_val[l];
return;
}
int mid=(l + r) / 2;
build(l, mid, tot * 2); ////遞歸左節點
build(mid + 1, r, tot * 2 + 1);////遞歸右節點

Node[tot].val = Node[tot * 2].val+Node[tot * 2 + 1].val; ////區間求和
}

void interval_plus(int targ_l, int targ_r, int val, int l, int r, int tot)
{
if(targ_l > r || targ_r < l)return; ////無交集直接return
else if(targ_l <= l && targ_r >= r) Node[tot].lazy += val;////打lazy標記
else
{
int len = max(0, min(targ_r,r) - max(targ_l,l) + 1); ////求出區間[targ_l, targ_r]與[l, r]的交集長度 更新節點值
Node[tot].val += len*val; //更新節點

int mid = (l + r) / 2;
interval_plus(targ_l, targ_r, val, l, mid, tot*2); ////遞歸左節點
interval_plus(targ_l, targ_r, val, mid + 1, r, tot*2 + 1);////遞歸右節點
}
}

int interval_query(int targ_l, int targ_r, int l, int r, int tot)
{
if(Node[tot].lazy)
{
if(l != r) ////如果該節點有子節點
{
Node[tot*2].lazy += Node[tot].lazy; ////左子節點打延遲標記
Node[tot*2+1].lazy += Node[tot].lazy;////右子節點打延遲標記
Node[tot].val += (Node[tot].r - Node[tot].l+1) * Node[tot].lazy; ？////更新節點值
Node[tot].lazy = 0; ////清空當前節點延遲標記
}
else ////如果該點沒有子節點
{
Node[tot].val += Node[tot].lazy;
Node[tot].lazy = 0;
}
}

if(targ_l > r || targ_r < l)return 0;
if(targ_l <= l && targ_r >= r)return Node[tot].val; ////如果當前節點包含於目標區間中，返回值

int mid=(l + r) / 2;
return interval_query(targ_l, targ_r, l, mid, tot * 2) + interval_query(targ_l, targ_r, mid + 1, r, tot * 2 + 1);
}
};

區間最值代碼：

class interval_play{
public:
class Segtree{
public:
int val, l, r, lazy;
}Node[maxn * 4 + 100];

int ini_val[maxn];
void init(int n)
{
for(int i = 1;i <= n * 4 + 100;i++)Node[i].lazy = 0;
}
void build(int l, int r, int tot)
{
Node[tot].l = l; Node[tot].r = r;
if(l == r)
{
Node[tot].val = ini_val[l];
return;
}
int mid=(l + r) / 2;
build(l, mid, tot * 2);
build(mid + 1, r, tot * 2 + 1);
Node[tot].val = max( Node[tot * 2].val, Node[tot * 2 + 1].val );
}

void interval_plus(int targ_l, int targ_r, int val, int l, int r, int tot)
{
if(targ_l > r || targ_r < l)return;
else if(targ_l <= l && targ_r >= r)
{
if(l!=r)
{
Node[tot*2].lazy += val;////點下面的打lazy標記
Node[tot*2+1].lazy += val;
}
Node[tot].val+=val;

int uptot=tot/2; ////更新祖先節點存儲的最值
while(uptot)
{
Node[uptot].val = max(Node[uptot*2].val, Node[uptot*2+1].val);
uptot/=2;
}
}
else
{
int mid = (l + r) / 2;
interval_plus(targ_l, targ_r, val, l, mid, tot*2);
interval_plus(targ_l, targ_r, val, mid + 1, r, tot*2 + 1);
}
}

int interval_query(int targ_l, int targ_r, int l, int r, int tot)
{
if(Node[tot].lazy)
{
if(l != r)
{
Node[tot*2].lazy += Node[tot].lazy;
Node[tot*2+1].lazy += Node[tot].lazy;
Node[tot].val += Node[tot].lazy;
Node[tot].lazy = 0;
}
else
{
Node[tot].val += Node[tot].lazy;
Node[tot].lazy = 0;
}
}

if(targ_l > r || targ_r < l)return 0;
if(targ_l <= l && targ_r >= r)return Node[tot].val;

int mid=(l + r) / 2;
int a=interval_query(targ_l, targ_r, l, mid, tot * 2);
int b=interval_query(targ_l, targ_r, mid + 1, r, tot * 2 + 1);
return max(a,b);
}
};

推薦閱讀：