###### tags: `MDCPP講義` # 講義-線段樹-區間修改 **Author : 謝侑哲** --- 先來複習一下之前的內容 ---- 線段樹的功能是甚麼? ---- 維護動態的區間值 ---- 線段樹的核心想法是甚麼? ---- 二分搜、DFS、小區間合併成大區間 ---- 做一次單點修改的時間複雜度? ---- O(logN)  ---- 複習完啦，那讓我們進入正題 --- 區間修改 ---- 以你們目前學到的東西 如果要做到區間修改你們會怎麼做? ---- 把一個區間的每個點都做一次區間修改? ---- 他的時間複雜度會是多少? ---- O(NlogN) ---- 雖然看起來還不錯，但或許還能更好? --- 懶人標記 ---- 懶人標記 顧名思義是給懶人用的東西 ---- 懶人?想到甚麼? ---- - 盡可能地做更少事情 - 能拖的事情一拖再拖 ---- 這些就是懶人標記的核心理念 - 把修改的工作變得越少越好 - 把修改的工作一拖再拖 ---- 要怎麼做到? ---- 或許我們可以不用修改區間內每個數的值? ---- [3,6]區間通通+1?  ----  總共用了4次logN ---- 找到最低限度描述區間的塊數  用了2次logN ---- 這樣的話，要查詢[2,3]區間怎麼辦  ---- 來看看我們查詢的路徑  ---- 可以發現一件事 查詢的時候，最終還是會經過上層抵達到下層  這樣當我們要用到應該被修改得更小區間時 必定會經過被我們加過值的那個區間 ---- 既然修改跟查詢都會走同個路徑抵達同個點 那我們不如把它和在一起做? ---- 在經過某個區間往下時，判斷該區間是否被修改，有則將修改值下傳   ---- 這樣的複雜度會是多少? ---- 因為查詢時修改是順便做的事情 因此基本上不列入複雜度的計算 ---- 最糟的情況 ---- 以區間長8為例  ---- 讓我們稍微移動一下他 ---- 是不是有一種分兩半分兩半再分兩半的味道  所以最後出來的複雜度會是O(logN) 比起對每個點做一次修改的O(NlogN)快了N倍 ---- 知道了概念，接下來就是怎麼寫了呢 --- code時間 ---- ```cpp= ``` ----