引入：
我們經常會遇到需要維護一個序列的問題，例如，給定一個整數序列，每次操作會修改某個位置或某個區間的值，或是詢問你序列中的某個區間內所有數的和，或許你可能回去暴力出奇跡或者使用前綴和，但是當資料很大時，時間復雜度明顯是受不了的，那么，就需要引入一種時間復雜度相對較小的資料結構 ——線段樹
目錄
基礎
├ 關于線段樹
├ 建樹
├ 區間查詢
└ 單點修改
進階
├ 延遲標記
│ └ 區間修改 單點查詢
└ 區間修改 區間查詢
├ 標記下傳
└ 標記永久化
注：本文用到了位運算優化常數，不會的小伙伴可看這篇博客【傳送門】
Ⅰ 基礎篇
一、關于線段樹
線段樹是一課二叉樹樹上的每一個結點對應序列的一段區間，如下圖：
不難發現，根節點對應的區間時[0,n-1]，而每個結點對應一個區間[l,r]，且當l=r時，該結點為葉結點，無左右兒子，否則令 mid = (l + r) / 2 ,則左兒子對應的區間為[l,mid]，右兒子為[mid+1,r]，同時，也不難發現，最后一行有n個結點，倒數第二行有n/2個結點，倒數第三行有n/4個結點，以此便可以推出一個線段樹有n+n/2+n/4+...+1=2*n+1個結點，但是要注意，線段樹陣列務必要開4倍，設線段樹的深度為h，那么h為O(logn)級別，當我們需要維護的序列長度為2的整數次冪時，這個線段數為滿二叉樹，否則最后一層可能不滿
二、建樹
注：接下來的一系列操作都以求區間和為例
設序列a：5,3,7,9,6,4,1,2，我們將其用線段樹構建出來，即
對應的區間和如圖
從圖中可以看出除葉結點區間和為它本身外，其他節點的區間和均為其左右兒子區間和之和，以此，可以通過遞回建樹，并在遞回后對其區間和進行維護
1 void build(int k,int l,int r){ //k為結點編號，l為區間左端點，r為區間右端點 2 if (l == r){ //如果該點為葉結點 3 sum[k] = a[l]; //區間和即為本身 4 return; 5 } 6 int mid = l + r >> 1; //取中間值，位運算優化常數 7 build(k << 1,l,mid); //構建左子樹 8 build(k << 1 | 1,mid + 1,r); //構建右子樹 9 sum[k] = sum[k << 1] + sum[k << 1 | 1]; //維護該區間區間和 10 }
三、區間查詢
如果我們要查詢區間和[0,6]，那么我們需訪問3個區間
那么在查詢程序中，會有以下三種情況
├ 當前區間與需查詢區間無交集，回傳 0
├ 當前區間被需查詢區間完全包含，回傳該結點對應區間和
└ 當前區間與需查詢區間有交集，但不被完全包含，遞回其左右子樹進行查詢
1 int query(int k,int x,int y,int l,int r){ //k為結點編號，x為當前區間左端點，y為當前區間右端點， 2 //l為需查詢區間左端點，r為需查詢區間右端點 3 if (x > r || y < l) return 0; //如果無交集，回傳0 4 if (x >= l && y <= r) return sum[k]; //如果完全包含，回傳該結點區間和 5 int res = 0,mid = x + y >> 1; 6 res = query(k << 1,x,mid,l,r); //遞回左子樹 7 res += query(k << 1 | 1,mid + 1,y,l,r); //遞回右子樹 8 return res; 9 }
四、單點修改
假設要將a1加2，那么我們要重新計算4個結點的值
||
\/
那么，在修改時可以用遞回的形式修改
在遞回中，可能會有以下幾種情況
├ 當前區間不包括需修改區間，直接回傳
├ 找到需修改的葉結點，修改，回傳
└ 有包含，但不是葉結點，遞回修改左右子樹
1 void change(int k,int l,int r,int p,int v){ 2 if (l > p || r < p) return; //若該區間不包含需修改點，直接回傳 3 if (l == r && l == p){ //若當前即為需修改結點 4 sum[l] += v; //修改 5 return; 6 } 7 int mid = l + r >> 1; 8 change(k << 1,l,mid,p,v);//遞回修改左子樹 9 change(k << 1 | 1,mid + 1,r,p,v);//遞回修改右子樹 10 sum[k] = sum[k << 1] + sum[k << 1 | 1];//維護區間和 11 }
Ⅱ 進階篇
一、延遲標記
有時我們需要解決的不只是單點修改、區間詢問，而是區間修改、區間詢問，那么單純使用以上的方法已經無法解決問題了，因為我們沒有辦法高效完成區間修改
以區間內所有數同時加上一個值，以及單點詢問為例進行引入
區間修改，單點查詢
考慮在每個結點上維護一個值addsum，表示這個結點所對應的區間內的所有數都加上了addsum，注意到根節點到葉結點[i,i]的路徑會經過所有包含點[i,i]的區間對應結點，并且路徑上所有結點都包括[i,i]這個點，所以路徑經過的所有結點的addsum的值加起來便是當前結點的值
1）區間修改
我們還是采用遞回的方式，對所求區間進行修改，我們在遞回時，會遇上以下幾種情況：
├ 當前區間不包括所修改區間，直接回傳
├ 需修改區間完全包含當前區間，給當前區間的addsum加上需加的值
└ 否則對該結點的兩個子樹進行遞回
1 void modify(int k,int l,int r,int x,int y,int v){//給區間[x,y]加上v 2 if (l > y || r < x) return; //無交集，直接回傳 3 if (l >= x && r <= y){//完全包含 4 addsum[k] += v; 5 return; 6 } 7 int mid = l + r >>1; 8 modift(k << 1,l,mid,x,y,v);//遞回左子樹 9 modift(k << 1 | 1,mid + 1,r,x,y,v);//遞回右子樹 10 }
2）單點查詢
在查詢時，要從根結點查詢至目標結點，會有以下幾種情況
├ 當前為葉子結點（需查詢結點），回傳當前結點的addsum值
├ 目標結點編號小于等于當前結點對應區間的中點編號，說明目標結點在左子樹，回傳遞回左子樹得到的值加上該點的
│ addsum
└ 否則說明在右子樹，回傳遞回右子樹得到的值加上該點的addsum
1 int query(int k,int l,int r,int p){ 2 if (l == r) return addsum[k]; 3 int mid = l + r >> 1; 4 if (p <= mid) 5 return query(k << 1,l,mid,p) + addsum[k]; 6 else 7 return query(k << 1 | 1,mid + 1,r,p) + addsum[k]; 8 }
再回到區間修改區間查詢這一問題上，此時打標記的方法也不可用了，若是遍歷所有會產生影響的結點并將其加起來，復雜度無法接受
那么常用的方法有兩種：一是標記下傳，二是標記永久化，這倆兄弟有個非常nb的名字——Lazy-Tag（懶標記）
二、區間修改 區間查詢
1）標記下傳
執行修改操作時，我們找到對應的結點，修改add(addsum)，并且得到更新的sum值，而這個結點所有的祖先都能通過 sum[k]=sum[k*2]+sum[k*2+1] 得到當前修改后正確的區間和，而這個結點的子節點無法立即更新，因為這樣的子節點太多，所以時間復雜度他又炸了，，，
解決的方案是（敲黑板）：當我們用到這些子結點的資訊時再進行更新，其實就是在某個結點遞回下去，將當前節點的add下傳到兩個子結點，更新兩個子結點的sum和add，并將當前結點的add清零，這樣操作以后，當我們訪問一個節點時，根節點到他的路徑上的add值都已經下傳更新到它的sum上了，所以它的sum便是它對應的區間和，
1 》 打標記（這里這是單純的打標記）
我們在給一個數打標記時，給他打上了標記，就意味著它疫檢合格了（不是下面的所有子節點都加上了這個數，那么它的區間和便要進行維護（l為區間左端點，r為區間右端點，v為所加的數），他的區間和變成了 sum[k] += (r-1+1) *v
1 void Add(int k,int l,int r,int v){ 2 add[k] += v; 3 sum[k] += (r - l + 1) * v; 4 }
2 》 標記下傳
我們這里又雙叒叕用遞回實作，如果需下傳的這個結點的add為0，跳出；否則下傳至左右子樹（其實就是呼叫一下剛剛的Add）
注意：記得將該點add清零！！！
1 void pushdown(int k,int l,int r,int mid){ 2 if (add[k] == 0) return; 3 Add(k << 1,l,mid,add[k]); 4 Add(k << 1 | 1,mid + 1,r,add[k]); 5 add[k] = 0; 6 }
3 》 區間修改
我們這里又雙叒叕用遞回實作；
他會有以下幾種情況：
├ 需修改區間完全包含當前區間，給當前區間打標記，就可以回傳了
└ 在不完全包含的情況下，先下傳一下標記，之后又有兩種情況，最后維護一下該節點區間和
├ 需修改區間的左邊界在當前區間中點左邊，遍歷一次左子樹
└ 需修改區間的右邊界在當前區間中點右邊，遍歷一次右子樹
1 void modify(int k,int l,int r,int x,int y,int v){ 2 if (l >= x && r <= y) return Add(k,l,r,v); 3 int mid = l + r >> 1; 4 pushdown(k,l,r,mid); 5 if (x <= mid) modify(k << 1,l,mid,x,y,v); 6 if (mid < y) modify(k << 1 | 1,mid + 1,r,x,y,v); 7 sum[k] = sum[k << 1] + sum[k << 1 | 1]; 8 }
4 》 區間查詢
我們這里又雙叒叕用遞回實作；
他會有以下幾種情況：
├ 需查詢區間完全包含當前區間，就可以回傳當前區間和
└ 在不完全包含的情況下，先下傳一下標記，之后又有兩種情況，定義res儲存結果
├ 如需查詢區間的左邊界在當前區間中點左邊，遍歷一次左子樹，res加一次
└ 如需查詢區間的右邊界在當前區間中點右邊，遍歷一次右子樹，res加一次
1 int query(int k,int l,int r,int x,int y){ 2 if (l >= x && r <= y) 3 return sum[k]; 4 int mid = l + r >> 1; 5 int res = 0; 6 pushdown(k,l,r,mid); 7 if (x <= mid) 8 res += query(k << 1,l,mid,x,y); 9 if (mid < y) 10 res += query(k << 1 | 1,mid + 1,r,x,y); 11 return res; 12 }
2）標記永久化
另一種方法是不下傳add標記，改為在詢問程序中計算每個遇到的節點對當前詢問的影響，為了保證詢問的時間復雜度，子節點的影響須在修改操作時就計算好，因此實際上，sum這個值表示這個區間內所有的數共同加上的值，sum表示這個區間內除了add之外其他值的和，
當然，區間的add值可能有一部分在祖先結點上，這在遞回時累加即可，與區間修改單點查詢相似
1 void modify(int k,int l,int r,int x,int y,int v){ //區間修改 2 if (l >= x && r <= y){ 3 add[k] += v; 4 return; 5 } 6 sum[k] += (min(r,y) - max(l,x) + 1) * v; 7 int mid = l + r >> 1; 8 if (x <= mid) modify(k << 1,l,mid,x,y,v); 9 if (mid < y) modify(k << 1 | 1,mid + 1,r,x,y,v); 10 } 11 int query(int k,int l,int r,int x,int y){ //查詢 12 if (l >= x && r <= y) 13 return sum[k] + (r - l + 1) * add[k]; 14 int mid = l + r >> 1; 15 int res = (min(r,y) - max(l,x) + 1) * add[k]; 16 if (x <= mid) 17 res += query(k << 1,l,mid,x,y); 18 if (mid < y) 19 res += query(k << 1 | 1,mid + 1,r,x,y); 20 return res; 21 }
驗證題目：【戳這里】
如果您有什么見解或疑問，歡迎在評論區提出(￣▽￣)／
第一次發布時間：2019.11.28 完成度：45%
第二次發布時間：2019.12.5 完成度：80%
第三次發布時間：2019.12.8 初版已完成
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/84916.html
標籤：C++