線段樹可以用來做 \(\log n\) 的區間修改、區間查詢
只要有結合律的資訊都可以用線段樹進行維護
其主要分為 build、update、query、push、pull 等函式組成
當不需要更詳細的資訊時，可以使用懶標記來記錄大致訊息
在線段樹中儲存的編號有兩種表達形式
0-based: id*2+1 / id*2+2
1-based: id*2 / id*2+1
id 為當前線段樹節點的編號
l、r 代表當前第 id 個節點在原陣列的區間
ql、qr 代表當前查詢的區間
以下為 1-based 的範例程式碼
int n; // 節點數
struct Node {
int data, tag;
Node() : data(0), tag(0) {}
};
vector<Node> seg;
int get_val(int l, int r, int id) {
return seg[id].data + seg[id].tag * (r-l+1);
}
void pull(int l, int r, int id) {
int m = (l+r)>>1;
seg[id].data = get_val(l, m, id<<1) + get_val(m+1, r, id<<1|1);
}
void push(int l, int r, int id) {
seg[id].data += seg[id].tag * (r-l+1);
seg[id<<1].tag += seg[id].tag;
seg[id<<1|1].tag += seg[id].tag;
seg[id].tag = 0;
}
void build(vector<int> &v, int l = 0, int r = n-1, int id = 1) {
if (l == r) return void(seg[id].data = v[l]);
int m = (l+r)>>1;
build(v, l, m, id<<1);
build(v, m+1, r, id<<1|1);
seg[id].data = seg[id<<1].data + seg[id<<1|1].data;
}
void update(int ql, int qr, int v, int l = 0, int r = n-1, int id = 1) {
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) return void(seg[id].tag += v);
push(l, r, id);
int m = (l+r)>>1;
update(ql, qr, v, l, m, id<<1);
update(ql, qr, v, m+1, r, id<<1|1);
pull(l, r, id);
}
int query(int ql, int qr, int l = 0, int r = n-1, int id = 1) {
if (l > qr || r < ql) return 0;
if (l >= ql && r <= qr) return get_val(l, r, id);
push(l, r, id);
int m = (l+r)>>1;
return query(ql, qr, l, m, id<<1) + query(ql, qr, m+1, r, id<<1|1);
}
signed main() {
cin >> n;
vector<int> v(n);
seg.assign(n<<2|1, Node());
for (auto &i : v) cin >> i;
build(v);
cout << query(0, 3) << '\n';
update(1, 3, 5);
cout << query(0, 3) << '\n';
}
這代表線段樹可以用來求區間和、乘積、最小最大值、最大公因數等等
