一，什么是線段樹？

• 線段樹是怎樣的樹形結構?

　　線段樹是一種二叉搜索樹，而二叉搜索樹，首先滿足二叉樹，即每個結點最多有兩顆子樹，并且是一顆搜索樹，我們要知道，線段樹的每個結點都存儲了一個區(qū)間，也可以理解成一個線段，而搜索，就是在這些線段上進行搜索操作得到你想要的答案。

• 線段樹能夠解決什么樣的問題？

　　線段樹的適用范圍很廣，可以在線維護修改以及查詢區(qū)間上的最值，求和。對于線段樹來說，每次更新以及查詢的時間復雜度為O(logN)。

• 線段樹和其他RMQ算法的區(qū)別

　　常用的解決RMQ問題有ST算法，二者預處理時間都是O(NlogN)

(詳見ST算法解決BMQ問題詳解)，而且ST算法的單次查詢操作是O(1)，看起來比線段樹好多了，但二者的區(qū)別在于線段樹支持在線更新值，而ST算法不支持在線操作。

1. 靜態(tài)的區(qū)間詢問：ST表

2. 動態(tài)的區(qū)間詢問：線段樹/樹狀數組

靜態(tài)指的是，數字 不會發(fā)生 改變
動態(tài)指的是，在 查詢過程中，數字可能會發(fā)生一定程度的 修改

---

二,線段樹的基本操作

建樹

思路

首先，我們得先明白幾件事情:

　每個結點存什么

結點下標是什么

如何建樹

下面我以一個簡單的求一段區(qū)間的最大值來描述上面的三個概念。

　　對于a[1~6] = {1,8,6,4,3,5}來說，線段樹如上所示，紅色代表每個結點存儲的區(qū)間，藍色代表該區(qū)間最值。

　　可以發(fā)現，每個葉子結點的值就是數組的值，每個非葉子結點的度都為二，且左右兩個孩子分別存儲父親一半的區(qū)間。每個父親的存儲的值也就是兩個孩子存儲的值的最大值。

　　那么結點到底是如何存儲區(qū)間的呢，以及如何快速找到非葉子結點的孩子以及非根節(jié)點的父親呢，這里也就是理解線段樹的重點以及難點所在，線段樹你只要理解了結點與結點之間的關系便能很快理解線段樹的基本知識。

　　對于一個區(qū)間[l,r]來說，最重要的數據當然就是區(qū)間的左右端點l和r，但是大部分的情況我們并不會去存儲這兩個數值，而是通過遞歸的傳參方式進行傳遞。這種方式可以直接用數組存樹，那這里怎么快速使用下標找到左右子樹呢?

　　對于上述線段樹，我們增加綠色數字為每個結點的下標

　　則每個結點下標如上所示，這里你可能會問，為什么最下一排的下標直接從9跳到了12，因為中間其實是有兩個空間的呀??！

雖然沒有使用，但是他已經開了兩個空間，這也是為什么線段樹建樹需要2*2k（2k-1 < n < 2k)空間，一般會開到4*n的空間防止RE。

　　仔細觀察每個父節(jié)點和子節(jié)點下標的關系，不難發(fā)現以下規(guī)律

l = fa*2 （左子樹下標為父節(jié)點下標的兩倍）
r = fa*2+1（右子樹下標為父節(jié)點下標的兩倍+1）

那么明白了數組如何存線段樹,結點間的關系,

建樹時每次遞歸就要先判斷l是否等于r,等于就說明是葉子節(jié)點,也就是區(qū)間是[l,l],直接賦值成a[l]/a[r]，再返回。

否則就遞歸構造左兒子結點和遞歸構造右兒子結點,最后更新父節(jié)點。

是不是覺得其實很簡單。

詳細代碼

void bui(int id,int l,int r)//創(chuàng)建線段樹,id表示存儲下標,區(qū)間[L,r]
{
  if(l == r)//左端點等于右端點，即為葉子節(jié)點(區(qū)間長度為1)，直接賦值即可
  {
    tr[id] = a[l];
    return ;
  }
// 否則將當前區(qū)間中間拆開成兩個區(qū)間
  int mid = (l + r) / 2;//mid則為中間點，左兒子的結點區(qū)間為[l,mid],右兒子的結點區(qū)間為[mid + 1,r]
  bui(id * 2,l,mid); //遞歸構造左兒子結點
  bui(id * 2 + 1,mid + 1,r); //遞歸構造右兒子結點
// 左右兩個區(qū)間計算完成以后
// 合并到當前區(qū)間
  tr[id] = min(tr[id * 2],tr[id * 2 + 1]);//更新父節(jié)點
}

看完代碼是不是很清晰，這里也建議自己再次手動實現一遍理解遞歸的思路。

區(qū)間查詢

思路

我們知道線段樹的每個結點存儲的都是一段區(qū)間的信息 ，如果我們剛好要查詢這個區(qū)間，那么則直接返回這個結點的信息即可，比如對于上面線段樹，如果我直接查詢[1,6]這個區(qū)間的最值，那么直接返回根節(jié)點信息返回13即可，但是一般我們不會湊巧剛好查詢那些區(qū)間，比如現在我要查詢[2,5]區(qū)間的最值，這時候該怎么辦呢，我們來看看哪些區(qū)間被[2,5]包含了。

　　一共有5個區(qū)間，而且我們可以發(fā)現[4,5]這個區(qū)間已經包含了兩個子樹的信息([4,4],[5,5])，所以我們需要查詢的區(qū)間只有三個，分別是[2,2],[3,3],[4,5]，到這里你能通過更新的思路想出來查詢的思路嗎? 我們還是從根節(jié)點開始往下遞歸，如果當前結點是被要查詢的區(qū)間包含了的，則返回這個結點的信息，這樣從根節(jié)點往下遞歸，時間復雜度也是O(logN)。

詳細代碼

//id 表示樹節(jié)點編號，l r 表示這個節(jié)點所對應的區(qū)間
//x y表示查詢的區(qū)間
int find(int id,int l,int r,int x,int y)
{
  //需要查詢的區(qū)間[x,y]將當前區(qū)間[l,r]包含的時候
  if(x <= l && r <= y) return tr[id];
  int mid = (l + r) / 2,ans = -INT_MAX;
   // 如果需要查詢左半區(qū)間
  if(x <= mid) ans = min(ans,find(id * 2,l,mid,x,y));   
  // 如果需要查詢右半區(qū)間
  if(y > mid) ans = min(ans,find(id * 2 + 1,mid + 1,r,x,y));
  return ans;
}

　　如果你能理解建樹的過程，那么這里的區(qū)間查詢也不會太難理解。還是建議再次手動實現。

單點更新

思路

很簡單,就是從根節(jié)點遞歸去找a[x],找到了就返回,并再返回的一路上不斷更新其父節(jié)點的max值。

詳細代碼

// id 表示樹節(jié)點編號，l r 表示這個節(jié)點所對應的區(qū)間
// 將 a[x] 修改為 v
// 線段樹單點更新
void gexi(int id, int l, int r, int x, int v)
{
// 找到長度為 1 的區(qū)間才返回
  if (l == r)
  {
    tr[id] = v;
    return;
  }
//否則找到 x 在左區(qū)間或者右區(qū)間去更新
  int mid = (l + r) / 2;
  if (x <= mid) gexi(id * 2, l, mid, x, v);// 需要修改的值在左區(qū)間
  else gexi(id * 2 + 1, mid + 1, r, x, v);// 需要修改的值在右區(qū)間
  tr[id] = max(tr[id * 2], tr[id * 2 + 1]);
}

區(qū)間更新

意思

在線段樹中會遇到區(qū)間更新的情況，例如 在區(qū)間求和問題中，令[a,b]區(qū)間內的值全部加c，若此時再采用單點更新的方法，就會耗費大量時間，這個時候就要用到懶標記(lazy標記)來進行區(qū)間更新了。

建樹

這個操作根普通的一模一樣

思路(更新)

懶標記（lazy-tag），又叫做延遲標記。

設 當前結點對應區(qū)間[l, r]，待更新區(qū)間[a, b]

　當 a ≤ l ≤ r ≤ b，即 [l, r]∈[a,b]時，不再向下更新，僅更新當前結點，并在該結點加上懶標記，當必須得更新/查詢該結點的左右子結點時，再利用懶標記的記錄向下更新（pushdown)——懶標記也要向下傳遞，然后移除該結點的懶標記。

這樣就不用每次都更新到葉子結點，減少了大量非必要操作，從而優(yōu)化時間復雜度。

具體舉個栗子:

就比如發(fā)壓歲錢,一次操作是太爺爺要發(fā)給[1,3]1塊壓歲錢,那么先發(fā)到爺爺手里,但是爺爺很懶

想著:反正這Q是我們家族的(要發(fā)Q的區(qū)間包含了爺爺管的區(qū)間),我就暫時收這了! ψ(｀?′)ψ 暫時不想下放,于是將lazy標記+1(太爺爺發(fā)的Q數),并且因為爺爺節(jié)點儲存的是以他根的樹的子節(jié)點的Q總數,所以他自己的sumv自然要+1*3(太爺爺發(fā)的Q數*爺爺代表的區(qū)間長度r-l+1)；

然后不要忘記遞歸回去時還要將太爺爺的sumv更新。

那么此時這棵樹就變成了這樣:

然后太爺爺一天突然心情大好,于是又發(fā)了一些錢,也就是給[2,3]2塊壓歲錢,那么先會發(fā)到爺爺手里。但是爺爺發(fā)現這筆Q要發(fā)放的區(qū)間不是由他管理,而是由他的兒孫中的一個管理,所以爺爺只能先將手中的壓歲Q下放,在遞歸左右孩子(因為如果不先把壓歲Q下放的話后面更新的值會錯)。 ＞﹏＜

在這里插一句嘴QwQ:下放操作是這樣的,首先將id的左孩子的lazy+他的lazy,再將id左孩子的Q+它、他下放的Q*左孩子區(qū)間長度(右孩子的這2步操作同理)(可以看做這個家族的所有人都很懶

),最后不要忘了還要把lazy[id]清空(詳見代碼)

下放后:

我們繼續(xù)。當到了叔叔的區(qū)間時會發(fā)現:叔叔的左區(qū)間<太爺爺要發(fā)壓歲Q的左區(qū)間,也就是說叔叔即他的兒孫并不會被太爺爺發(fā)壓歲Q。所以繼續(xù)遞歸到爸爸的區(qū)間,此時爸爸發(fā)現這Q是我們家族的(要發(fā)Q的區(qū)間包含了爸爸管的區(qū)間),而他傳承了爺爺的"優(yōu)良"傳統(tǒng),也很懶 o(*￣▽￣*)ブ 暫時不想下放,于是將lazy標記+2(太爺爺發(fā)的Q數),并且因為爸爸節(jié)點儲存的是以他根的樹的子節(jié)點的Q總數,所以他自己的sumv自然要+1*2(太爺爺發(fā)的Q數*爸爸代表的區(qū)間長度r-l+1)；

然后不要忘記遞歸回去時還要將,爺爺,太爺爺的sumv更新。

那么此時這棵樹變成了這樣:

代碼(更新)

void push_up(int id)
{
  sumv[id] = sumv[id * 2] + sumv[id * 2 + 1];
}
void push_down(int id,int l,int r)
{
  if(lazy[id])//如果id有l(wèi)azy標記
  {
    int mid = (l + r) / 2;
    lazy[id * 2] += lazy[id];//將它的左孩子的lazy加上它的lazy
    lazy[id * 2 + 1] += lazy[id];//將它的右孩子的lazy加上它的lazy
    sumv[id * 2] += lazy[id] * (mid - l + 1);//左孩子的Q+它下放的Q*區(qū)間長度
    sumv[id * 2 + 1] += lazy[id] * (r - mid);
    lazy[id] = 0;//清空lazy標記
  }
}
void qjgx(int id,int l,int r,int x,int y,int v)//id:目前查到的節(jié)點編號  目前區(qū)間為[l,r]  目標是講[x,y]的所有數+v
{
  if(l >= x && r <= y)//[l,r]被[x,y]包含了
  {
    lazy[id] += v;//暫時不下放Q,加進lazy標記中
    sumv[id] += v * (r - l + 1);//將Q收入囊中
    return ;
  }
  push_down(id,l,r);//要來更新下面節(jié)點了,趕緊下放Q
  int mid = (l + r) / 2;
  if(x <= mid) qjgx(id * 2,l,mid,x,y,v);//因為只有x<=mid(即[l,mid]有一部分是被[x,y]覆蓋了的)才需要去更新[l,mid]
  if(y > mid) qjgx(id * 2 + 1,mid + 1,r,x,y,v);
  push_up(id);//子節(jié)點更新完之后父節(jié)點當然也要更新(上升操作)
}

思路(查詢)

書接上回。一次太爺爺去別人家做客時發(fā)現大人們總是把過年的壓歲Q"幫"孩子們收著,美名曰"保管"(其實就是強占),于是太爺爺決定去查詢一下孩子們的壓歲Q有沒有發(fā)放到位￣へ￣

比如他要查詢的是[1,2]那么首先要查詢的是爺爺,然后發(fā)現爺爺的區(qū)間[1,3]并沒有被包含在[1,2]中,所以先下放lazy(因為此時爺爺lazy為0,所以相當與沒下放 ╮(╯-╰)╭ )然后爺爺就繼續(xù)查詢到叔叔,發(fā)現叔叔的去見被完全包含在了[1,3]中,所以返回叔叔的值4,然后從爺爺繼續(xù)遞歸到了爸爸,發(fā)現爸爸的區(qū)間[2,3]并沒有被包含在[1,2]中,所以還是下放lazy(不然查到子節(jié)點時自己私拿孩子壓歲Q的事就露陷了！

(っ °Д °;)っ

于是爸爸趕緊下放lazy,于是這棵樹就變成了這樣:

然后遞歸左孩子,發(fā)現被包含在了[1,2]中,返回4，右孩子沒被包含,返回,然后爸爸返回4,爺爺返回4+4=8,所以最后太爺爺收到了8，大功告成!(●ˇ?ˇ●)

代碼(查詢)

int find(int id,int l,int r,int x,int y)//id:目前查到的節(jié)點編號  目前區(qū)間為[l,r]  目標是求出[x,y]的和
{
  if(x <= l && r <= y) return sumv[id];//[l,r]被[x,y]包含了
  push_down(id,l,r);//要查到id的子節(jié)點了,趕緊下放
  int mid = (l + r) / 2,ans = 0;
  if(x <= mid) ans += find(id * 2,l,mid,x,y);//ans+=左孩子和
  if(y > mid) ans += find(id * 2 + 1,mid + 1,r,x,y);//ans+=右孩子和
  return ans;
}

---

三,例題

題目1(單點更新)

思路

先輸入a數組,再創(chuàng)建線段樹,最后每次輸入時判斷p是否為1,是則輸出find(1,1,m,x,y);否則gexi(1,x,1,m,y)。

代碼

#include <bits/stdc++.h>
using namespace std;
int tr[10000001];
int a[10000001];
void bui(int id,int l,int r)//創(chuàng)建線段樹,id表示存儲下標,區(qū)間[L,r]
{
  if(l == r)
  {
    //葉子
    tr[id] = a[l];
    return ;
  }
  int mid = (l + r) / 2;
  bui(id * 2,l,mid);
  bui(id * 2 + 1,mid + 1,r);
  tr[id] = min(tr[id * 2],tr[id * 2 + 1]);
}
//id 表示樹節(jié)點編號，l r 表示這個節(jié)點所對應的區(qū)間
//x y表示查詢的區(qū)間
int find(int id,int l,int r,int x,int y)
{
  //需要查詢的區(qū)間[x,y]將當前區(qū)間[l,r]包含的時候
  if(x <= l && r <= y) return tr[id];
  int mid = (l + r) / 2,ans = INT_MAX;
  if(x <= mid) ans = min(ans,find(id * 2,l,mid,x,y));
  if(y > mid) ans = min(ans,find(id * 2 + 1,mid + 1,r,x,y));
  return ans;
}
void gexi(int k,int id,int l,int r,int num)
{
  if(l == r)
  {
    tr[k] = num;
    return ;
  }
  int mid = (l + r) / 2;
  if(id <= mid)
    gexi(k * 2,id,l,mid,num);
  else
    gexi(k * 2 + 1,id,mid + 1,r,num);
  tr[k] = min(tr[k * 2],tr[k * 2 + 1]);
}
signed main()
{
  int n,m;
  cin>>m>>n;
  for(int i = 1; i <= m; i++) cin>>a[i];
  bui(1,1,m);
  while(n--)
  {
    int x,y,p;
    cin>>p>>x>>y;
    if(p == 1) cout<<find(1,1,m,x,y)<<' ';
    else gexi(1,x,1,m,y);
  }
  return 0;
}

例題2(區(qū)間更新)

思路

套模板即可。

代碼

#include <bits/stdc++.h>
#define int long long
using namespace std;
int sumv[10000001],n,m,a[10000001],lazy[10000001];
void push_up(int id)
{
  sumv[id] = sumv[id * 2] + sumv[id * 2 + 1];
}
void push_down(int id,int l,int r)
{
  if(lazy[id])//如果id有l(wèi)azy標記
  {
    int mid = (l + r) / 2;
    lazy[id * 2] += lazy[id];//將它的左孩子的lazy加上它的lazy
    lazy[id * 2 + 1] += lazy[id];//將它的右孩子的lazy加上它的lazy
    sumv[id * 2] += lazy[id] * (mid - l + 1);//左孩子的Q+它下放的Q*區(qū)間長度
    sumv[id * 2 + 1] += lazy[id] * (r - mid);
    lazy[id] = 0;//清空lazy標記
  }
}
void bui(int id,int l,int r)
{
  if(l == r)//葉子節(jié)點
  {
    sumv[id] = a[l];
    return ;
  }
  int mid = (l + r) / 2;
  bui(id * 2,l,mid);//遞歸創(chuàng)建左子樹
  bui(id * 2 + 1,mid + 1,r);//遞歸創(chuàng)建右子樹
  sumv[id] = sumv[id * 2] + sumv[id * 2 + 1];//左子樹和+右子樹和
}
void qjgx(int id,int l,int r,int x,int y,int v)//id:目前查到的節(jié)點編號  目前區(qū)間為[l,r]  目標是講[x,y]的所有數+v
{
  if(l >= x && r <= y)//[l,r]被[x,y]包含了
  {
    lazy[id] += v;//暫時不下放Q,加進lazy標記中
    sumv[id] += v * (r - l + 1);//將Q收入囊中
    return ;
  }
  push_down(id,l,r);//要來更新下面節(jié)點了,趕緊下放Q
  int mid = (l + r) / 2;
  if(x <= mid) qjgx(id * 2,l,mid,x,y,v);//因為只有x<=mid(即[l,mid]有一部分是被[x,y]覆蓋了的)才需要去更新[l,mid]
  if(y > mid) qjgx(id * 2 + 1,mid + 1,r,x,y,v);
  push_up(id);//子節(jié)點更新完之后父節(jié)點當然也要更新(上升操作)
}
int find(int id,int l,int r,int x,int y)//id:目前查到的節(jié)點編號  目前區(qū)間為[l,r]  目標是求出[x,y]的和
{
  if(x <= l && r <= y) return sumv[id];//[l,r]被[x,y]包含了
  push_down(id,l,r);//要查到id的子節(jié)點了,趕緊下放
  int mid = (l + r) / 2,ans = 0;
  if(x <= mid) ans += find(id * 2,l,mid,x,y);//ans+=左孩子和
  if(y > mid) ans += find(id * 2 + 1,mid + 1,r,x,y);//ans+=右孩子和
  return ans;
}
signed main()
{
  cin>>n>>m;
  for(int i = 1; i <= n; i++) cin>>a[i];
  bui(1,1,n);
  while(m--)
  {
    int k,x,y,p;
    cin>>p>>x>>y;
    if(p == 1)
    {
      cin>>k;
      qjgx(1,1,n,x,y,k);
    }
    else cout<<find(1,1,n,x,y)<<'\n';
  }
  return 0;
}

---

四,結語

怎么樣?看懂了嗎?看懂了的話請留個贊吖！文章來源地址http://www.zghlxwxcb.cn/news/detail-446419.html