Hướng dẫn giải của Truy vấn số lớn nhất trong dãy số
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for qmax: Truy vấn số lớn nhất trong dãy số
Hiểu bài toán
Bài toán yêu cầu xử lý hai loại truy vấn trên một dãy số gồm n phần tử: (1) cập nhật giá trị tại một vị trí và (2) tìm giá trị lớn nhất trong một đoạn [u, v]. Với n và Q lớn (lên tới 10^6 và 10^5), các giải thuật duyệt tuần tự cho mỗi truy vấn loại 2 sẽ quá chậm. Cần một cấu trúc dữ liệu hiệu quả để xử lýboth loại truy vấn trong thời gian logarithmic.
Các cách tiếp cận
Cách Segment Tree (Cây Phân Đoan)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
ll a[N], ST[4*N];
void build(int id, int l, int r) {
if (l == r) {
ST[id] = a[l];
return;
}
int m = (l + r) >> 1;
build(id<<1, l, m);
build(id<<1|1, m+1, r);
ST[id] = max(ST[id<<1], ST[id<<1|1]);
}
void update(int id, int l, int r, int pos, int val){
if (pos<l || r<pos) return;
if (l==r) {ST[id]=val; a[l]=val; return;}
int m=(l+r)>>1;
if (pos<=m) update(id<<1,l,m,pos,val);
else update(id<<1|1,m+1,r,pos,val);
ST[id]=max(ST[id<<1],ST[id<<1|1]);
}
int get(int id, int l, int r, int u, int v){
if (r<u || v<l) return INT_MIN;
if (u<=l && r<=v) return ST[id];
int m=(l+r)>>1;
return max(get(id<<1,l,m,u,v),get(id<<1|1,m+1,r,u,v));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
vector<ll> answers;
while (q--) {
int type; cin >> type;
if (type == 1) {
int i, x; cin >> i >> x;
update(1, 1, n, i, x);
} else {
int u, v; cin >> u >> v;
answers.push_back(get(1, 1, n, u, v));
}
}
for (size_t i = 0; i < answers.size(); ++i) {
if (i > 0) cout << ' ';
cout << answers[i];
}
return 0;
}
- Time Complexity: O(Q log n)
- Space Complexity: O(n)
Segment Tree là cấu trúc dữ liệu cây nhị phân điển hình cho bài toán RMQ (Range Maximum Query). Mỗi nút cây lưu giá trị lớn nhất của một đoạn. Xây dựng cây ban đầu mất O(n). Mỗi truy vấn cập nhật hoặc truy vấn max đều duyệt qua độ cao cây (log n nút), do đó độ phức tạp tổng thể là O(Q log n). Đây là phương án tối ưu và phổ biến nhất cho bài toán này.
Cách Sparse Table
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
const int LOG = 20;
ll a[N];
int ST[LOG][N];
int lg[N];
void build(int n) {
lg[1] = 0;
for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
for (int i = 1; i <= n; i++) ST[0][i] = a[i];
for (int j = 1; j < LOG; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
ST[j][i] = max(ST[j-1][i], ST[j-1][i + (1 << (j-1))]);
}
}
}
int query(int u, int v) {
int len = v - u + 1;
int j = lg[len];
return max(ST[j][u], ST[j][v - (1 << j) + 1]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(n);
vector<ll> answers;
while (q--) {
int type; cin >> type;
if (type == 1) {
// Update không hỗ trợ trong Sparse Table Static
// Giải pháp: Phải rebuild toàn bộ hoặc dùng Segment Tree
// Segment Tree là lựa chọn đúng đắn ở đây
} else {
int u, v; cin >> u >> v;
answers.push_back(query(u, v));
}
}
return 0;
}
- Time Complexity: O(1) truy vấn, O(n log n) xây dựng
- Space Complexity: O(n log n)
Sparse Table cho phép trả lời truy vấn Range Maximum Query trong thời gian O(1) bằng cách pre-calculate các khối 2^k. Tuy nhiên, điểm yếu lớn nhất của Sparse Table là không hỗ trợ cập nhật động (dynamic updates). Nếu có cập nhật, ta phải xây dựng lại bảng từ đầu (O(n log n)), rất chậm. Do đó, Sparse Table chỉ phù hợp với bài toán tĩnh (không có type 1).
Cách Brute Force (Duyệt tuần tự)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
ll a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
vector<ll> answers;
while (q--) {
int type; cin >> type;
if (type == 1) {
int i, x; cin >> i >> x;
a[i] = x;
} else {
int u, v; cin >> u >> v;
ll mx = a[u];
for (int k = u + 1; k <= v; k++) {
if (a[k] > mx) mx = a[k];
}
answers.push_back(mx);
}
}
for (ll x : answers) cout << x << ' ';
return 0;
}
- Time Complexity: O(Q * n)
- Space Complexity: O(n)
Giải pháp ngây thơ nhất là lưu mảng và với mỗi truy vấn loại 2, ta duyệt từ u đến v để tìm max. Với Q lên tới 10^5 và n lên tới 10^6, độ phức tạp O(Q * n) sẽ thực hiện khoảng 10^11 phép tính, chắc chắn gây Timeout. Tuy nhiên, đây là cơ sở để hiểu tại sao cần Segment Tree.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(Q log n) | O(n) | Segment Tree (Cây Phân Đoan) |
| 2 | O(1) truy vấn, O(n log n) xây dựng | O(n log n) | Sparse Table |
| 3 | O(Q * n) | O(n) | Brute Force (Duyệt tuần tự) |
Bài học kinh nghiệm
- Bài toán là ứng dụng điển hình của cấu trúc dữ liệu Segment Tree cho các bài toán truy vấn đoạn (Range Queries) với cập nhật điểm (Point Updates).
- Segment Tree hoạt động bằng cách chia dãy thành các đoạn nhỏ hơn và lưu thông tin (max) của mỗi đoạn, cho phép lấy thông tin của đoạn lớn bằng cách kết hợp thông tin của các đoạn con.
Lỗi thường gặp
- Lỗiindexing: Segment Tree thường được cài đặt với index bắt đầu từ 1 để dễ dàng tính toán con (2id, 2id+1). Cần chú ý khi nhập xuất dữ liệu.
- Giá trị âm: Khi khởi tạo giá trị âm cho các nút lá hoặc khi tính toán return value cho các segment không chứa phần tử, cần dùng một giá trị âm đủ nhỏ (ví dụ: -1e18 hoặc INT_MIN).
Bình luận