CHUYÊN ĐỀ: CẤU TRÚC DỮ LIỆU NÂNG CAO
Đặng Tuấn Thành
Trường THPT Chuyên Nguyễn Tất Thành, tỉnh Yên Bái
Interval Tree là công cụ rất hữu dụng được sử dụng nhiều trong các bài toán trên dãy
số, hoặc được quy về các bài toán xử lí trên dãy số, đặc biệt là các bài toán có nhiều
công việc cần xử lí và nhiều truy vấn xen kẽ nhau.
Phần lí thuyết về Interval Tree đã được trình bày rất rõ ràng ở nhiều tài liệu do các
chuyên gia, đồng nghiệp dạy bồi dưỡng học sinh giỏi chia sẻ, nên tôi mạn phép
không đề cập tại đây.
Do năng lực có hạn nên tôi không viết hoặc nghĩ ra những bài tập mới mà có sử dụng
Interval Tree để giải được. Vì thế, trong chuyên đề này thực chất là các bài tập tôi sưu
tầm, biên tập thành tập tài liệu để phục vụ trong công tác giảng dạy bồi dưỡng HSG
môn Tin học. Ở đây, tôi trích dẫn các bài tập nguồn từ SPOJ, Codeforce và nhiều
nguồn khác. Với mỗi bài tập tôi đề cập đến ba vấn đề:
Tóm tắt đề bài rõ ràng
Thuật toán tốt
Code demo (nếu có).
Khi áp dụng tài liệu này vào giảng dạy, tôi thường bỏ phần “code demo” để không
“làm hỏng học sinh”, chỉ phát đề cho học sinh. Với mỗi bài tập, sau khi học sinh
nghiên cứu và đề xuất ý tưởng (hoặc code nộp mà chưa AC), tôi dẫn dắt, đưa ra giải
thuật của bài toán đó để học sinh “ngấm” bài toán hơn. Dần dần học sinh nắm được
tư tưởng Interval Tree và ứng dụng linh động vào các bài toán khác.
Tôi cũng xin trích dẫn các tài liệu tôi tham khảo để biên tập thành chuyên đề này:
http://laptrinh.ntu.edu.vn/Problem/List
http://codeforces.com/problemset
http://vn.spoj.com/problems/oi/
https://onlylove97.wordpress.com/category/it/
https://doraemonvodanh.wordpress.com/category/thuat-toan/segment-tree/baitap-interval-tree/
1
Quyển: Một số vấn đề chú ý môn Tin học – Nhóm tác giả của Đại học Vinh
2
Ứng dụng Interval Tree để giải các bài toán sau:
Bài 1. Phần tử thứ K http://vn.spoj.com/problems/YPKTH/
Cho dãy số A có N phần tử nguyên phân biệt.
Cho Q truy vấn, mỗi truy vấn có dạng: L R K
Yêu cầu: mỗi truy vấn xuất ra phần tử lớn thứ K sau khi sắp xếp các phần tử AL,
AL+1, …, AR theo thứ tự tăng dần.
Giới hạn:
1 ≤ N, Q ≤ 105
|Ai| ≤ 109 với 1 ≤ i ≤ N
1≤L≤R≤N
1 ≤ K ≤ R-L+1
Input:
-
Dòng đầu tiên chứa số N.
-
Dòng tiếp theo chứa N số A1, A2, …, AN.
-
Dòng tiếp theo chứa số Q.
-
Q dòng tiếp theo, mỗi dòng chứa 3 số L, R, K.
Output:
Q dòng, mỗi dòng chứa câu trả lời cho một truy vấn theo thứ tự nhập vào.
Ví dụ:
Input
Output
7
2
2154368
6
4
4
122
3
374
462
551
Thời gian chạy: 1s-3s
THUẬT TOÁN :
3
Dùng Segment Tree với mỗi nút lưu lại dãy con từ l->r đã được sort. Dùng vector cho
mỗi nút để giảm bộ nhớ: mỗi nút sẽ xuất hiện logN lần trên cây, do đó bộ nhớ là
NlogN. Có thể tạo cây trong O(NlogN), mỗi lần hợp hai nút con lại ta trộn hai đoạn
con trong O(n+m) với n, m là kích thước của hai đoạn con.
Với mỗi truy vấn ta làm như sau: Xét các giá trị (gọi là res) có trong dãy bằng cách
chặt nhị phân, (nút 1 thực chất đã sort dãy tăng dần nên có thể chặt nhị phân trên nút
1), đếm xem trong đoạn l..r có bao nhiêu phần tử nhỏ hơn nó, nếu nhỏ hơn k tức là
phải tìm số lớn hơn nữa và tương tự. Với mỗi lần truy vấn l..r thì ta lại chặt nhị phân
những nút nằm trong đoạn l..r để tìm phần tử lớn nhất ≤ res đồng thời kiểm tra xem
res có mặt cũng như đếm số lượng phần tử nhỏ hơn res (Chú ý là các phần tử là phân
biệt). Điều kiện để res là nghiệm chính là cnt == k-1 (cnt là số lượng số < res) và tìm
thấy res trong đoạn l..r.
Code demo: http://ideone.com/GTScHq
#include
using namespace std;
typedef long long ll;
typedef int64_t ll;
typedef pair ii;
#define EL printf("\n")
#define pb push_back
#define mp make_pair
#define X first
#define Y second
typedef vector data;
const int N = 100100;
int
n, q, a[N], L, R, k, res, cnt, f;
data
t[4*N], nil;
data combine(data u, data v)
{
data ans = nil;
int i = 0, j = 0;
while (i < u.size() and j < v.size()) {
if (u[i] < v[j]) ans.pb(u[i++]);
else ans.pb(v[j++]);
}
while (i < u.size()) ans.pb(u[i++]);
while (j < v.size()) ans.pb(v[j++]);
return ans;
}
void build(int k, int l, int r)
void get(int node, int l, int r)
{
if (r < L or R < l) return ;
if (L ≤ l and r ≤ R) {
int i = 0, j = t[node].size()-1, pos = -1;
while (i ≤ j) {
int mid = (i+j)/2;
if (t[node][mid] ≤ res) {
pos = mid;
i = mid+1;
}
else j = mid-1;
}
if (pos == -1) return ;
if (t[node][pos] == res) f = true;
cnt += pos + 1;
if (t[node][pos] == res) cnt--;
return ;
}
int mid = (l+r)/2;
get(node*2,l,mid);
get(node*2+1,mid+1,r);
}
int main()
{
//freopen("YPKTH.INP","r",stdin);
//freopen("YPKTH.OUT","w",stdout);
scanf("%d", &n);
4
{
for (int i=1;i≤n;i++) scanf("%d", &a[i]);
build(1,1,n);
scanf("%d", &q);
while (q--) {
scanf("%d%d%d", &L,&R,&k);
int l = 0, r = t[1].size()-1;
while (l ≤ r) {
int mid = (l+r)/2;
res = t[1][mid];
cnt = 0;
f = 0;
get(1,1,n);
if (cnt == k-1 and f) {
printf("%d\n", res);
break;
}
if (cnt < k) l = mid+1; else r = mid-1;
}
}
return 0;
if (l == r) {
t[k].pb(a[l]);
return ;
}
int mid = (l+r)/2;
build(k*2, l, mid);
build(k*2+1, mid+1, r);
t[k] = combine(t[k*2], t[k*2+1]);
}
}
Bài 2. Đoạn con có tổng lớn nhất http://vn.spoj.com/problems/GSS/
Cho dãy số a[1], a[2], ..., a[n] (|a[i]| ≤ 15000, n ≤ 50000).
Hàm q(x, y) = max { tổng(a[i]+a[i+1]+...+a[j]), x ≤ i ≤ j ≤y }.
Cho m câu hỏi dạng x, y (1 ≤ x ≤ y ≤ n), (m ≤ 50000) -> hãy tính các q(x, y).
Input
- Dòng đầu là n.
- Dòng thứ hai là dãy a.
- Dòng thứ 3 là m.
- m dòng tiếp theo mỗi dòng là 1 cặp số x, y.
Output
Lần lượt ghi ra các q(x, y) tương ứng. Mỗi kết quả ghi trên 1 dòng.
Example
Input:
3
-1 2 3
1
12
5
Output:
2
Thời gian chạy: 0.100s
Thuật toán: Sử dụng Segment Tree
Một nút lưu các giá trị :
sum : tổng đoạn
pre : tổng lớn nhất của đoạn tiền tố
suf : tổng lớn nhất của đoạn hậu tố
ans : tổng lớn nhất của đoạn
Công thức hợp hai nút trên cây như sau :
res.sum = l.sum + r.sum;
res.pre = max(l.pre, l.sum + r.pre);
res.suf = max(r.suf, r.sum + l.suf);
res.ans = max(l.ans, r.ans, l.suf + r.pre);
Code demo:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
.PDF 
27 
1356 
99 
