【線段樹】線段樹入門之入門
https://zh.visualgo.net/fenwicktree
上面的都是些基本的線段樹結構，但只有這些并不能做什么，就好比一個程序有輸入沒輸出榴鼎，根本沒有任何用處。
最簡單的應用就是記錄線段是否被覆蓋咳短，并隨時查詢當前被覆蓋線段的總長度踩晶。那么此時可以在結點結構中加入一個變量int count；代表當前結點代表的子樹中被覆蓋的線段長度和宋下。這樣就要在插入（刪除）當中維護這個count值嗡善，于是當前的覆蓋總值就是根節(jié)點的count值了。
另外也可以將count換成bool cover学歧；支持查找一個結點或線段是否被覆蓋罩引。
實際上，通過在結點上記錄不同的數據枝笨，線段樹還可以完成很多不同的任務袁铐。例如，如果每次插入操作是在一條線段上每個位置均加k横浑，而查詢操作是計算一條線段上的總和剔桨，那么在結點上需要記錄的值為sum。
這里會遇到一個問題：為了使所有sum值都保持正確徙融，每一次插入操作可能要更新O(N）個sum值洒缀，從而使時間復雜度退化為O(N）。
解決方案是Lazy思想：對整個結點進行的操作欺冀，先在結點上做標記帝洪，而并非真正執(zhí)行，直到根據查詢操作的需要分成兩部分脚猾。
根據Lazy思想葱峡，我們可以在不代表原線段的結點上增加一個值toadd，即為對這個結點龙助，留待以后執(zhí)行的插入操作k值的總和砰奕。對整個結點插入時，只更新sum和toadd值而不向下進行提鸟，這樣時間復雜度可證明為O(logN）军援。
對一個toadd值為0的結點整個進行查詢時，直接返回存儲在其中的sum值称勋；而若對toadd不為0的一部分進行查詢胸哥，則要更新其左右子結點的sum值，然后把toadd值傳遞下去赡鲜，再對這個查詢本身空厌，左右子結點分別遞歸下去庐船。時間復雜度也是O(nlogN）。
線段樹
最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門毛嫉，熙熙樓的掌柜王于貴愁眉苦臉地迎上來诽俯，“玉大人，你說我怎么就攤上這事狱庇。” “怎么了恶耽？”我有些...
- 正文 為了忘掉前任涌萤，我火速辦了婚禮淹遵，結果婚禮上，老公的妹妹穿的比我還像新娘负溪。我一直安慰自己透揣，他們只是感情好，可當我...
- 文/花漫 我一把揭開白布川抡。 她就那樣靜靜地躺著辐真，像睡著了一般。 火紅的嫁衣襯著肌膚如雪崖堤。 梳的紋絲不亂的頭發(fā)上侍咱，一...
- 文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼麸粮！你這毒婦竟也來了溉苛？” 一聲冷哼從身側響起，我...
- 正文 年R本政府宣布违诗，位于F島的核電站，受9級特大地震影響疮蹦，放射性物質發(fā)生泄漏诸迟。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一愕乎、第九天 我趴在偏房一處隱蔽的房頂上張望阵苇。 院中可真熱鬧，春花似錦感论、人聲如沸绅项。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽趁怔。三九已至，卻和暖如春薪前，著一層夾襖步出監(jiān)牢的瞬間润努，已是汗流浹背。 一陣腳步聲響...
推薦閱讀更多精彩內容
- 線段樹(又稱區(qū)間樹), 是一種高級數據結構屋确，他可以支持這樣的一些操作: 查找給定的點包含在了哪些區(qū)間內 查找給定的...
