1. 首頁 > 生活百科 > >

基礎&進階 線段樹學習筆記（一） | P3372 【模板】線段樹 1 題解

生活百科

什么是線段樹線段樹是一棵二叉樹，每個結點存儲需維護的信息，一般用于處理區間最值、區間和等問題 。
線段樹的用處對編號連續的一些點進行修改或者統計操作，修改和統計的復雜度都是 O(log n) 。
基礎線段樹（+ 懶標記）為什么不寫沒有懶標記的版本？因為我太菜的不會寫 因為有懶標記的版本更實用啦 。

  • P3372 【模板】線段樹 1
這是一道線段樹區間修改 ， 區間查詢的模板題，維護的是區間和 。
1. 建樹void build(int rt, int L, int R) { l[rt] = L, r[rt] = R; if (L == R) {sum[rt] = a[L];return ; } int mid = L + R >> 1; build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R); update(rt);}作為一棵最最普通的線段樹 ， 它有一個性質，對于每個結點 x，它的左兒子的編號是 x * 2 （即代碼中的 x << 1），右兒子的編號是 x * 2 + 1 （即代碼中的 x << 1 | 1） 。代碼中的 l 和 r 數組用于記錄編號為 rt 的點所管轄的區間的左右端點 。update 是什么？它是用子節點的數據更新自身的數據 ， 以保證正確性 。
  • update 的具體實現
void update(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}它在后續的操作中也會用到 。
2. 修改void change(int rt, int L, int R, int x) { if (L <= l[rt] && r[rt] <= R) {sum[rt] += (r[rt] - l[rt] + 1) * x;lazy[rt] += x;return ; } pushdown(rt); if (L <= r[rt << 1]) change(rt << 1, L, R, x); if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x); update(rt);}其中傳入的參數 L 和 R 表示需修改的區間的左右端點 ， x 表示這個區間上要加的數 。if (L <= l[rt] && r[rt] <= R) 意為當該點管轄的區間被需修改的區間全覆蓋時 ， 直接修改這個點上記錄的區間和，并打上懶標記，不繼續下傳，以保證效率 。（懶標記就是一種記錄修改操作的 tag，用于節省時間 。）pushdown 操作意為該點管轄的區間不完全覆蓋于需修改的區間時，下傳懶標記 。（為什么現在才下傳？因為懶標記就是這么用的 因為后面的更改會用到該點的子節點的數據 ， 如果懶標記不下傳，后面的修改操作就會出現問題 。）下面的兩個 if 是什么？if (L <= r[rt << 1]) 表示左兒子的區間中有部分（或全部）包含于詢問區間，需統計 。（如果還是沒看出來就翻回去看看定義和性質吖）那么是不是就知道 if (l[rt << 1 | 1] <= R) 是什么了？對，它表示的是右兒子的區間中有部分（或全部）包含于詢問區間，需統計 。傳的參數為什么是這樣不用我說了吧？
  • pushdown 的具體實現
void pushdown(int rt) { if (!lazy[rt]) return ; sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt]; sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt]; lazy[rt << 1] += lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; lazy[rt] = 0; update(rt);}在下傳懶標記時給子節點的區間和加上 懶標記的值 × 子節點的區間大小 。（給該子節點的管轄區間的所有數都加上懶標記的值，那么該區間的區間和就會加上 懶標記的值 × 區間長度 。）同時，給子節點的懶標記都加上自己的懶標記的值 。（沒錯我還是給你吊在那里，不給你傳到底）記得清空自己的懶標記值并更新自己的區間和 。
3. 查詢ll query(int rt, int L, int R) { if (L <= l[rt] && r[rt] <= R) return sum[rt]; pushdown(rt); ll res = 0; if (L <= r[rt << 1]) res += query(rt << 1, L, R); if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R); return res;}查詢其實和修改很像 。（不妨肉眼觀查一下）在該結點所管轄的區間完全被覆蓋時，直接返回區間和 。若未被完全覆蓋，則下傳懶標記，分左右兒子考慮，統計總答案并返回值 。是不是 so easy？
于是你愉快地切了這題 。
完整代碼，點擊查看【基礎&進階 線段樹學習筆記（一） | P3372 【模板】線段樹 1 題解】#include <bits/stdc++.h>using namespace std;#define ll long long#define pii pair<int, int>inline ll read() { ll s = 0, w = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') w = -1; c = getchar();} while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar(); return s * w;}const int N = 100010;int n, m, a[N];struct SegmentTree { ll sum[N << 2], lazy[N << 2]; int l[N << 2], r[N << 2]; void update(int rt) {sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void pushdown(int rt) {if (!lazy[rt]) return ;sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt], lazy[rt << 1] += lazy[rt];sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt], lazy[rt << 1 | 1] += lazy[rt];lazy[rt] = 0;update(rt); } void build(int rt, int L, int R) {l[rt] = L, r[rt] = R;if (L == R) {sum[rt] = a[L];return ;}int mid = L + R >> 1;build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R);update(rt); } void change(int rt, int L, int R, int x) {if (L <= l[rt] && r[rt] <= R) {sum[rt] += (r[rt] - l[rt] + 1) * x;lazy[rt] += x;return ;}pushdown(rt);if (L <= r[rt << 1]) change(rt << 1, L, R, x);if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x);update(rt); } ll query(int rt, int L, int R) {if (L <= l[rt] && r[rt] <= R) return sum[rt];pushdown(rt);ll res = 0;if (L <= r[rt << 1]) res += query(rt << 1, L, R);if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R);return res; }} tree;int main() { n = read(), m = read(); for (int i = 1; i <= n; i++) a[i] = read(); tree.build(1, 1, n); while (m--) {int op = read();if (op == 1) {int l = read(), r = read(), x = read();tree.change(1, l, r, x);}if (op == 2) {int l = read(), r = read();printf("%lld\n", tree.query(1, l, r));} } return 0;}

推薦閱讀