線段樹學習筆記（基礎&進階）（一） | P3372 【模板】線段樹 1 題解
什麼是線段樹
線段樹是一棵二叉樹，每個結點存儲需維護的信息，一般用於處理區間最值、區間和等問題。
線段樹的用處
對編號連續的一些點進行修改或者統計操作，修改和統計的複雜度都是 O(log n)。
基礎線段樹（+ 懶標記）
為什麼不寫沒有懶標記的版本？
因為我太菜的不會寫 因為有懶標記的版本更實用啦。
這是一道線段樹區間修改，區間查詢的模板題，維護的是區間和。
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？
於是你愉快地切了這題。
完整代碼，點擊查看
#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;
}
現在，你學會了區間修改區間查詢的線段樹，不如想想 單點修改區間查詢 和 區間修改單點查詢 怎麼寫？（為什麼沒有單點修改單點查詢線段樹呢（小聲）
點擊繼續研究線段樹 – 線段樹學習筆記（基礎&進階）（二）（碼字中…）
