寫在前面的話

博主自己也算是學了一陣子線段樹了, 看到kuangbin線段樹專題 還沒有人進行過系統的整理, 所以自己想做這樣的一個專題, 把自己做題的思路和心得分享出來與大家一起交流.

在本文中您發現了錯誤也請在評論中指出. 如果您有疑惑同樣可以評論留言, 我會在看到后即時回復.

如果這篇博客幫助到了您, 這里也希望您能點一個大大的贊👍支持博主, 這樣也能讓這篇博客幫助到更多的人

題解部分(最下方有博主的板子)

做題順序: 按照下面題單順序從前往后做即可.

單點修改 + 區間查詢: 1 2 9
區間修改 + 根節點查詢: 5
區間修改 + 區間查詢: 3 8 11 12 13
區間染色: 4 6
需要合并區間的區間查詢: 7
需要轉化區間: 10(需要前綴知識 DFS序)
掃描線計算面積: 16 15
掃描線計算周長: 14
掃面線計算體積: 17(這個題大概率咕咕咕了)

題解:
1. HDU 1166 敵兵布陣
2. HDU 1754 I Hate It
3. POJ 3468 A Simple Problem with Integers
4. POJ 2528 Mayor’s posters
5. HDU 1698 Just a Hook
6. ZOJ 1610 Count the Colors
7. POJ 3264 Balanced Lineup
8. HDU 4027 Can you answer these queries?
9. HDU 1540 Tunnel Warfare
10. HDU 3974 Assign the task
11. HDU 4578 Transformation
12. HDU 4614 Vases and Flowers
13. HDU 4553 約會安排
14. POJ 1177 Picture
15. HDU 1255 覆蓋的面積
16. HDU 1542 Atlantis
17. [HDU 3642 Get The Treasury] 掃描線計算體積 摸了

線段樹模板

基礎線段樹

重點: 維護區間的某種屬性, 如: 前綴和 最大值 最小值等.

pushdown函數 (一般做一個重載) 作用: 由父親節點維護子節點, 下放懶標記.
當操作的區間需要分裂時調用. (在modify和ask函數中)

pushup函數 (根據需要選擇是否重載)(是否維護多種信息) 作用: 由子節點維護父親節點.
當子節點改變時, 需要調用, 以保證父親節點信息正確

build函數, 建樹, 推薦將樹中的所有數據都手動進行初始化, 避免可能因多組輸入產生的錯誤

modify函數, 修改函數. 在進行區間修改的時候, 區間分裂時不要忘記pushdown, 修改后應pushup

ask函數, 詢問函數, 當遇到區間合并問題時, 應當返回類型為節點類型.

/* 基礎數據結構 */ int w[N]; //初始化的值 struct node {int l, r; //維護區間ll sum; //維護的屬性ll lazy; //懶標記, 當前節點的懶標記不包括自己. }t[N << 2];/* 基礎函數 */ void pushdown(node& op, ll lazy) { //重載. 作用: 給當前節點加上懶標記 一定寫重載!!!op.sum += lazy * (op.r - op.l + 1); //維護當前節點屬性op.lazy += lazy; //累加懶標記 } void pushdown(int x) { if (!t[x].lazy) return;pushdown(t[x << 1], t[x].lazy), pushdown(t[x << 1 | 1], t[x].lazy);t[x].lazy = 0; //節點懶標記清空 }void pushup(node& p, node& l, node& r) { //重載. 作用: 把l, r區間信息合并得到父親節點pp.b = l.b + r.b; p.d = gcd(l.d, r.d); //涉及到區間合并的時候重載 } void pushup(int x) { pushup(t[x], t[x << 1], t[x << 1 | 1]); }void build(int l, int r, int x = 1) {t[x] = { l, r, w[l], 0... }; //特別注意, 如果有多組的情況, 懶標記一定要賦初值if (l == r) return;int mid = l + r >> 1;build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);pushup(x); //不要忘了!!! }void modify(int a, int c, int x = 1) { //單點修改, a為要修改的點, c為修改的值if (t[x].l == t[x].r /* && t[x].l == a */) {//修改操作, 這里不需要pushup了, 因為遞歸結束后會pushupreturn;}int mid = t[x].l + t[x].r >> 1;modify(a, c, x << 1 | (a > mid));pushup(x); } void modify(int l, int r, int c, int x = 1) { //區間修改if (l <= t[x].l && r >= t[x].r) {pushdown(t[x], c); //可以認為是對這個節點進行了一次pushdownreturn;}pushdown(x); //后續pushup需要根據子節點維護父親節點, 所以要下放懶標記int mid = t[x].l + t[x].r >> 1;if (l <= mid) modify(l, r, c, x << 1);if (r > mid) modify(l, r, c, x << 1 | 1);pushup(x); }auto ask(int l, int r, int x = 1) {if (l <= t[x].l && r >= t[x].r) {return t[x].sum/*t[x]*/; //若涉及到區間合并, 則返回節點類型}pushdown(x); int mid = t[x].l + t[x].r >> 1;/* 維護單值情況ll sum = 0;if (l <= mid) sum += ask(l, r, x << 1);if (r > mid) sum += ask(l, r, x << 1 | 1);return sum;*//* 涉及到區間合并的情況 */if (r <= mid) return ask(l, r, x << 1); //僅在左半部分if (l > mid) return ask(l, r, x << 1 | 1); //僅在右半部分auto left = ask(l, r, x << 1), right = ask(l, r, x << 1 | 1); //橫跨左右, 構造新區間node res; //注意p是否需要初始化某些值, 有的合并不局限于左右兒子pushup(res, left, right); //此時要把left和right合并為新的區間 return res; }

END

總結

以上是生活随笔為你收集整理的kuangbin线段树专题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。