線段樹當中的幾個重要操作

1.PushUp

上推操作：由子節點算父節點的信息

$pushup$ 操作的目的是為了維護父子節點之間的邏輯關系。當我們遞歸建樹時，對于每一個節點我們都需要遍歷一遍，并且電腦中的遞歸實際意義是先向底層遞歸，然后從底層向上回溯，所以開始遞歸之后必然是先去整合子節點的信息，再向它們的祖先回溯整合之后的信息。
我們在這兒就能看出來，實際上push_up是在合并兩個子節點的信息，所以需要信息滿足結合律！

2.PushDown

下沉操作，又稱為懶標記或延遲標記：由父節點計算子節點的信息

之所以稱為懶標記，是因為當我們在修改一個區間的信息的時候，我們不會把這個區間和它的所有子區間全都修改，而是在根節點的區間上標記一下（這就需要一個額外的信息 $add$ 來儲存我們的修改信息），在用到該區間的時候才進行修改。即延遲修改。

例如我們要修改區間 $[1,10]$，我們無須把它的子區間 $[1,5]$ 和 $[6,10]$ 以及 $[1,5]$ 和 $[6,10]$ 的子區間全部遞歸修改一番直到修改到葉子節點然后逐層回溯，這樣操作的時間復雜度是可以高達 $O(NlogN)$ 的。
我們可以直接在區間 $[1,10]$ 標記一下，表示我們修改了這個區間了，但是我們不對他的子區間進行操作，直到某一次查詢或者修改需要使用這個區間的時候，我們才修改這個區間并把它的修改下沉到子區間。

不過我的習慣是，當我們需要標記一個區間的時候，直接就把此區間修改了。

總而言之，懶標記的作用是記錄每次、每個節點要更新的值，也就是delta,但線段樹的優點不在于全記錄（全記錄依然很慢qwq），而在于傳遞式記錄：

整個區間都被操作，記錄在公共祖先節點上；只修改了一部分，那么就記錄在這部分的公共祖先上；

3.Build

將一段區間初始化為線段樹

4.Modify

1. 單點（$PushUp$）
2. 區間（$PushDown$ + $Pushup$）
   
   
   
   

5.Query

時間復雜度：$O(4\times logN)$
查詢某一段區間的信息

6.與樹狀數組的比較

線段樹的常數比樹狀數組
線段樹的 $logn$ 是 $4$ 倍的 $logn$
樹狀數組的 $logn$ 是 $1$ 倍的 $logn$
線段樹點修改和區間查詢的時間復雜度為

7.$up$和$down$操作的使用時機

主要是從定義出發

(1)$pushup$

$pushup$ 的定義是通過合并子節點的信息并上傳修改根節點的信息，只要修改子節點的信息，就要在回溯的過程中修改父節點的信息。

因此，$pushup$ 一般是在代碼的末尾出現，只有子節點都修改完成之后，才可以吧子節點的信息合并推到父節點上。

例如：

(1)建樹的過程中，如果區間可以繼續劃分，那么我們就要遞歸該根節點的左右區間，當遞歸左右區間結束的時候，就要 $pushup$ 合并返回子節點的信息。
(2)修改區間信息，如果我們修改的區間不能在當前區間直接完成修改，而是要在它的左右區間分別修改一部分，例如區間 $[1,10]$，我們要修改 $[4,7]$ ,就需要分別修改它的左子樹區間 $[1,5]$ 和右子樹區間 $[6,10]$。并在修改結束的時候 $pushup$ 合并子節點的修改信息返回到父節點。

(2)$pushdown$

$pushdown$的定義是下沉父節點的修改信息到子節點，只要父節點的信息被修改，就要下沉父節點的修改信息到子節點上。

因此， $pushdown$ 一般在代碼的頭出現，否則此時子節點的信息未被修改，或者說出現修改重疊的情況。

并且，使用 $pushdown$ 的時候一般都是在區間分裂的時候使用的。即，我們不能在當前區間直接完成操作，需要分別在它的左區間或者右區間或者兩個子區間進行操作。而由于我們使用了懶標記，只修改了根區間的信息，它的子區間還未修改，所以說我們要把它的修改信息下沉到子區間并修改和標記子區間。

例如：

(1)執行查詢操作，此時我們得到區間的一些信息，當然要把還未執行的操作執行一下。
(2)執行修改操作，這個不太好理解，雖然說我們的修改操作也可能會使用到兩個子區間的信息，但我們只是對區間加上一個懶標記，為什么還要把根區間的懶標記下沉呢？這是因為我們上面的 pushup 會出現在修改操作里，如果懶標記沒有下傳就會導致子節點的值沒有第一時間更新，父節點就會被錯誤的更新。

再舉個例子解釋一下第(2)點：

1. 初始化區間 $[1,10]$ 所有元素全為 $1$，建樹，維護兩個信息：$lazyTag$ 和 區間和 $sum$
2. 執行修改操作 $[1,10]$ 的每個元素都加上 $2$，此時區間元素全為3。我們的懶標記修改了區間 $[1,10]$ 的 $sum$，$sum[1,10]=30$，但此時區間 $[1,5],[6,10],...,[9,9],[10,10]$的值依然是初始狀態下的值。 最后 $pushup$ (由于 $[1,10]$ 為整個樹的根節點，所以此時 $pushup$ 啥都沒做)。
3. 再次執行修改操縱 $[1,5]$ 的每個元素都加上 $1$（不執行 $pushdown$），緊接著由于 $[1,5]$ 無法包含當前區間 $[1,10]$ ，分裂區間為 $[1,5],[6,10]$, 遞歸到左區間 $[1,5]$，此時正好包含該區間，修改區間 $[1,5]$ 的值為 $10$，然后 $pushup$ 該區間的修改信息到父區間 $[1,10]$, $sum[1,10]=sum[1,5]+sum[6,10]=10+5=15$,然后回溯到父區間 $[1,10]$，執行 $pushup$(由于是樹根不執行)，結束。
4. 最后我們發現第二次操作 $sum[1,10]=15$，甚至比第一次操作的 $sum$ 更小了，究其原因在于第一次操作給區間 $[1,10]$ 打上的懶標記沒有在第二次操作下沉到子區間，導致子區間實際上沒有執行第一次修改操作。
5. 如果我們在分裂區間之前執行 $pushdown$，那么此時有 $sum[1,5]=15,sum[6,10]=15$，然后執行第二次修改操作 $sum[1,5]=15+5=20$，最后合并區間 $[1,5],[6,10]$ 的和上傳到區間 $[1,10]$，此時 $sum[1,10]=20+15=35$ 就正確了
   
   
   
   

8.常見的SE錯誤來源

1. 數組空間沒有開四倍
2. $mid=l+r>>1$ 還是 $mid=tr[u].l+tr[u].r>>1$
3. $u<<1$ 或者 $u<<1|1$ 是否寫錯
4. $build$ 里面 $else$ 循環中，是否初始化 t r [ u ] = { l , r . . . } tr[u] =\{l, r... \} tr[u]={l,r...}

例題

1.區間加法

模板題

步驟二：思路

步驟三：代碼

2.區間乘法 + 區間加法

步驟一：題目描述

模板題

步驟二：思路

步驟三：代碼

3.區間最大公約數

步驟一：題目描述

結論

步驟二：思路

步驟三：代碼

4.最大連續字段和

步驟一：題目描述

維護額外信息

步驟二：思路

步驟三：代碼

4.區間最值

步驟一：題目描述

思維

步驟二：思路

步驟三：代碼