一、簡介線段樹
ps: _此處以詢問區間和為例。實際上線段樹可以處理很多符合結合律的操作。（比如說加法，a[1]+a[2]+a[3]+a[4]=(a[1]+a[2])+(a[3]+a[4])）
線段樹之所以稱為「樹」，是因為其具有樹的結構特性。線段樹由於本身是專門用來處理區間問題的（包括RMQ、RSQ問題等。
圖片來源於網際網路。
對於每一個子節點而言，都表示整個序列中的一段子區間；對於每個葉子節點而言，都表示序列中的單個元素信息；子節點不斷向自己的父親節點傳遞信息，而父節點存儲的信息則是他的每一個子節點信息的整合。
有沒有覺得很熟悉？對，線段樹就是分塊思想的樹化，或者說是對於信息處理的二進位化——用於達到O(logn)級別的處理速度，log以2為底。（其實以幾為底都只不過是個常數，可忽略)。而分塊的思想，則是可以用一句話總結為：通過將整個序列分為有窮個小塊，對於要查詢的一段區間，總是可以整合成k個所分塊與m個單個元素的信息的並(0≤k,m≤sqrt{n})。但普通的分塊不能高效率地解決很多問題，所以作為log級別的數據結構，線段樹應運而生。
Extra Tips
其實，雖然線段樹的時間效率要高於分塊但是實際上分塊的總合併次數不會超過sqrt{n}但是線段樹在最壞情況下的合併次數顯然是要大於這個時間效率的qwq。
~~但是畢竟也只是一個很大的常數而已~~
However,雖說如此，分塊的應用範圍還是要廣於線段樹的，因為雖然線段樹好像很快，但是它只能維護帶有結合律的信息，比如區間max/min、sum、xor之類的，但是不帶有結合律的信息就不能維護（且看下文分解）；而分塊則靈活得多，可以維護很多別的東西,因為實際上分塊的本質就是優雅的暴力qwq。
其實越暴力的算法可以支持的操作就越多、功能性就越強吶！~~你看n^2的暴力幾乎什麼都可以維護~~
二、逐步分析線段樹的構造實現
1、建樹與維護
由於二叉樹的自身特性，對於每個父親節點的編號i,他的兩個兒子的編號分別是2i和2i+1，所以我們考慮寫兩個O(1)的取兒子函數：
_
Extra Tips
1、此處的inline可以有效防止無需入棧的信息入棧，節省時間和空間。
2、二進位位左移一位代表著數值*2，而如果左移完之後再或上1，由於左移完之後最後一位二進位位上一定會是0，所以|1等價於+1。
~~用二進位運算不是為了裝X,相信我，會快的！~~
那麼根據線段樹的服務對象，可以得到線段樹的維護:
此處一定要注意，push up操作的目的是為了維護父子節點之間的邏輯關係。當我們遞歸建樹時，對於每一個節點我們都需要遍歷一遍，並且電腦中的遞歸實際意義是先向底層遞歸，然後從底層向上回溯，所以開始遞歸之後必然是先去整合子節點的信息，再向它們的祖先回溯整合之後的信息。(這其實是正確性的證明啦)
吶，我們在這兒就能看出來，實際上push_up是在合併兩個子節點的信息，所以需要信息滿足結合律！
那麼對於建樹，由於二叉樹自身的父子節點之間的可傳遞關係，所以可以考慮遞歸建樹（emmmm之前好像不小心劇透了qwq），並且在建樹的同時，我們應該維護父子節點的關係：
2、接下來談區間修改
為什麼不討論單點修改呢qwq?因為其實很顯然，單點修改就是區間修改的一個子問題而已，即區間長度為1時進行的區間修改操作罷了qwq
那麼對於區間操作，我們考慮引入一個名叫「lazy tag」（懶標記）的東西——之所以稱其「lazy」，是因為原本區間修改需要通過先改變葉子節點的值，然後不斷地向上遞歸修改祖先節點直至到達根節點，時間複雜度最高可以到達O(nlogn)的級別。但當我們引入了懶標記之後，區間更新的期望複雜度就降到了O(logn)的級別且甚至會更低.
（1）首先先來從分塊思想上解釋如何區間修改：
分塊的思想是通過將整個序列分為有窮個小塊，對於要查詢的一段區間，總是可以整合成k個所分塊與m個單個元素的信息的並(0<=k,m<=logn)(小小修改了一下的上面的前言qwq)
那麼我們可以反過來思考這個問題：對於一個要修改的、長度為l的區間來說，總是可以看做由一個長度為2 ^ logn 和剩下的元素（或者小區間組成）。那麼我們就可以先將其拆分成線段樹上節點所示的區間，之後分開處理：
如果單個元素被包含就只改變自己，如果整個區間被包含就修改整個區間
其實好像這個在分塊裡不是特別簡單地實現，但是在線段樹裡，無論是元素還是區間都是線段樹上的一個節點，所以我們不需要區分區間還是元素，加個判斷就好。
（2）懶標記的正確打開方式
首先，懶標記的作用是記錄每次、每個節點要更新的值，也就是delta,但線段樹的優點不在於全記錄（全記錄依然很慢qwq），而在於傳遞式記錄：
整個區間都被操作，記錄在公共祖先節點上；只修改了一部分，那麼就記錄在這部分的公共祖先上；如果四環以內只修改了自己的話，那就只改變自己。
畢竟，如果我們採用上述的優化方式的話，我們就需要在每次區間的查詢修改時pushdown一次，以免重複或者衝突或者爆炸qwq
那麼對於pushdown而言，其實就是純粹的pushup的逆向思維(但不是逆向操作)：
因為修改信息存在父節點上，所以要由父節點向下傳導lazy tag
那麼問題來了：怎麼傳導pushdown呢？這裡很有意思，開始回溯時執行pushup,因為是向上傳導信息；那我們如果要讓它向下更新，就調整順序，在向下遞歸的時候pushdown不就好惹~qwq：
對於複雜度而言，由於完全二叉樹的深度不超過logn，那麼單點修改顯然是O(logn)的，區間修改的話，由於我們的這個區間至多分logn個子區間，對於每個子區間的查詢是O(1)的，所以複雜度自然是O(logn)~~不過帶一點常數~~
3、那麼對於區間查詢
沒什麼好說的，由於是信息的整合，所以還是要用到分塊思想，我實在是不想再碼一遍了qwq
最後貼~~高清無碼的~~標程：
（還有，輸入大數據一定不要用不加優化的cin/cout啊）
本文發布於洛穀日報，特約作者：皎月半灑花
原文地址：https://pks-loving.blog.luogu.org/senior-data-structure-qian-tan-xian-duan-shu-segment-tree