Segment Tree là cây nhị phân lưu thông tin trên các đoạn của mảng. Mỗi node lưu kết quả tổng hợp (tổng, min, max,...) của một đoạn .
Độ phức tạp: cho cả truy vấn và cập nhật. Bộ nhớ .
Cài đặt cơ bản (cập nhật điểm, truy vấn đoạn)
struct SegTree {
int n;
vector<long long> tree;
SegTree(int n) : n(n), tree(4*n, 0) {}
void build(vector<int>& a, int node, int l, int r) {
if (l == r) { tree[node] = a[l]; return; }
int mid = (l + r) / 2;
build(a, 2*node, l, mid);
build(a, 2*node+1, mid+1, r);
tree[node] = tree[2*node] + tree[2*node+1];
}
void update(int node, int l, int r, int pos, long long val) {
if (l == r) { tree[node] = val; return; }
int mid = (l + r) / 2;
if (pos <= mid) update(2*node, l, mid, pos, val);
else update(2*node+1, mid+1, r, pos, val);
tree[node] = tree[2*node] + tree[2*node+1];
}
long long query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0; // ngoài đoạn
if (ql <= l && r <= qr) return tree[node]; // trong đoạn hoàn toàn
int mid = (l + r) / 2;
return query(2*node, l, mid, ql, qr)
+ query(2*node+1, mid+1, r, ql, qr);
}
};
// Sử dụng (chỉ số 0-based):
SegTree seg(n);
seg.build(a, 1, 0, n-1);
seg.update(1, 0, n-1, i, val);
long long s = seg.query(1, 0, n-1, l, r);
Lazy Propagation (cập nhật đoạn)
Khi cần cập nhật cả đoạn (cộng thêm , gán ,...), lazy propagation đưa độ phức tạp về :
- Mỗi node lưu thêm
lazy— phần chưa đẩy xuống con. - Trước khi đi xuống con, push down lazy.
struct LazySegTree {
int n;
vector<long long> tree, lazy;
LazySegTree(int n) : n(n), tree(4*n, 0), lazy(4*n, 0) {}
void push_down(int node, int l, int r) {
if (lazy[node] == 0) return;
int mid = (l + r) / 2;
tree[2*node] += lazy[node] * (mid - l + 1);
tree[2*node+1] += lazy[node] * (r - mid);
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
lazy[node] = 0;
}
// Cộng val vào mọi phần tử trong [ql, qr]
void update(int node, int l, int r, int ql, int qr, long long val) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
tree[node] += val * (r - l + 1);
lazy[node] += val;
return;
}
push_down(node, l, r);
int mid = (l + r) / 2;
update(2*node, l, mid, ql, qr, val);
update(2*node+1, mid+1, r, ql, qr, val);
tree[node] = tree[2*node] + tree[2*node+1];
}
long long query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return tree[node];
push_down(node, l, r);
int mid = (l + r) / 2;
return query(2*node, l, mid, ql, qr)
+ query(2*node+1, mid+1, r, ql, qr);
}
};
Thay đổi hàm kết hợp
Segment Tree có thể hỗ trợ nhiều loại truy vấn chỉ bằng cách thay hàm kết hợp:
// Min / Max thay vì tổng:
tree[node] = min(tree[2*node], tree[2*node+1]);
// Giá trị trả về khi ngoài đoạn: LLONG_MAX (cho min), LLONG_MIN (cho max)
// GCD:
tree[node] = __gcd(tree[2*node], tree[2*node+1]);
// Giá trị trả về khi ngoài đoạn: 0
Khi nào dùng Segment Tree thay Fenwick Tree?
- Cần truy vấn min hoặc max (Fenwick không hỗ trợ)
- Cần lazy propagation với logic phức tạp (gán giá trị, kết hợp nhiều loại cập nhật)
- Cần lưu thêm nhiều thông tin trên mỗi node
Bài tập minh họa
- Truy vấn — point update, range max query
Bình luận