Cấu trúc dữ liệu đặc biệt
HỘI THẢO KHOA HỌC CÁC TRƯỜNG THPT CHUYÊN
KHU VỰC DUYÊN HẢI & ĐỒNG BẰNG BẮC BỘ
LẦN THỨ VIII
CHUYÊN ĐỀ BỒI DƯỠNG HỌC SINH GIỎI
Người thực hiện: ÔN QUANG HÙNG
Đơn vị: Trường THPT Chuyên Nguyễn Bỉnh Khiêm - tỉnh Quảng Nam.
Quảng Nam, tháng 8 năm 2015
1
Cấu trúc dữ liệu đặc biệt
INTERVAL TREE(IT)
A. PHẦN LÝ THUYẾT
Interval tree (cây đoạn) là một cây nhị phân mỗi nút không phải là node lá đều có
hai nút con.
Giả sử nút A lưu thông tin của đoạn từ i..j thì 2 nút con của nó: A1; A2, lần lượt
lưu thông tin của các đoạn i..m và m+1..j, với m=(i+j) div 2 là phần tử giữa đoạn.
Để đơn giản ta dùng mảng 1 chiều T để biểu diễn cây với ý nghĩa:
Nút 1 là nút gốc
Nút d(nếu không là nút lá) thì có nút con trái: 2*d và nút con phải 2*d+1
Nút 1 lưu thông tin các đoạn 1..n(n: độ dài dãy số)
Vậy dễ hiểu nút 2 lưu thông tin đoạn [1..(n+1) div 2] và nút 3 sẽ lưu thông tin
đoạn [(n+1) div 2+1 .. n]
Một cách đệ quy thì ta thấy nút thứ d sẽ lưu thông tin của 1 đoạn xác định nào
đấy. Ví dụ với n=5 có đoạn [1..n]
2
Cấu trúc dữ liệu đặc biệt
Trên cây interval tree có hai thao tác quan trọng
Thao tác cập nhật thông tin(gọi truy vấn 1) trên đoạn [i..j]
Thao tác khai thác thông tin(gọi truy vấn 2) trên đoạn [i..j]
Ứng dụng của cây IT
Cây IT cho phép cập nhật và tìm kiếm các đoạn, khoảng rất hiệu quả
Cây IT còn kết hợp với cấu trúc Heap hoặc AVL để giải quyết một số bài toán
Đối với những bài toán liên quan đến dãy số; những dạng bài toán quy về dãy số;
bài toán hình học, .... đặc biệt những việc mà thường xuyên biến đổi và nhiều câu
hỏi (truy vấn) xen kẻ, thì cây IT rất hữu dụng.
Ví dụ:
Cho một dãy số nguyên A[1..N] gồm N phần tử(N<=105). Có M truy vấn gồm
hai loại:
Ci j: Thay phần tử thứ i bằng giá trị j.
Qi j: Xuất ra tổng các phần tử trong dãy số từ vị trí i đến vị trí j
Nhiệm vụ: Cho trước dãy số A[1..N] và M truy vấn trong file văn bản
DAYSO.INP. Hãy thực hiện các phép biến đổi trên dãy và ghi các kết quả ra file
DAYSO.OUT
Ví dụ
INPUT.INP
OUTPUT.OUT
53
5
12345
14
Q23
C37
Q14
Dùng cây IT để giải quyết vấn đề như sau:
Truy vấn 1:
Thủ tuc truyvan1(l,r,i,d:longint): trong đó l(đầu đoạn) và r(cuối đoạn); d(node
chứa dữ liệu); còn i là vị trí hay con gọi là phần tử thứ i mà cần gán giá trị v
Mỗi đoạn [l..r] sẽ có 3 khả năng so với đoạn [i..i] (sử dụng đoạn [i,i] cho dễ so
sánh)
o TH1: [l..r] [i,i] = thì bỏ qua không làm gì cả (exit)
3
Cấu trúc dữ liệu đặc biệt
o TH2: [l..r] =[i,i] (vừa khít hay l=r) thì ta gán T[d]:=v, lúc này v là giá trị
lớn nhất trên đoạn [i,i](d là node lá thì ta gán giá trị v vào)
o TH3: [l..r] không nằm trong [i,i] thì ta sang node con trái và node con
phải để cập nhật sau khi cập nhật xong hai node con thì tiếp theo tính cập nhật cho
node cha. Một cách đệ quy thì chắc hẳn phải gặp một trong hai trường hợp trên
Cứ mỗi truy vấn 1 thì ta cập nhật được giá trị v vào cây IT
Lời gọi truy vấn 1 bắt đầu từ node gốc truyvan1(1,n,i,1);
Thuật toán như sau:
{==========================================================}
procedure
truyvan1(l,r,i,d:longint);
var mid:longint;
begin
if (ir) then exit;
if (i=L)and(j=R) then
begin
inc(res,t[d]);
exit;
end;
mid:=(L+R) div 2;
truyvan2(L,mid,i,mid,2*d);
truyvan2(mid+1,R,mid+1,j,2*d+1);
end;
{==========================================================}
Nhận xét:
Ta nhận thấy mỗi truy vấn độ phức tạp xấp xỉ O(log(n))
Như vậy bài này nếu dùng interval tree độ phức tạp xấp xỉ O(mxlog(n))
5
Cấu trúc dữ liệu đặc biệt
B. PHẦN BÀI TẬP VẬN DỤNG
Bài 1
Cho một dãy số A[1..N] gồm N số nguyên đánh số từ 1 đến N là A[1], A[2], ...,
A[N]. Xét M yêu cầu gồm hai loại:
Ci j: Thay phần tử thứ i bằng giá trị j.
Qi j: Xuất ra phần tử lớn nhất trong dãy số từ vị trí i đến vị trí j
Nhiệm vụ: Cho trước dãy số A[1..N] và M yêu cầu trong file văn bản
MAXIJ.INP. Hãy thực hiện các phép biến đổi trên dãy và viết các kết quả ra file
MAXIJ.OUT
Dữ liệu vào: file MAXIJ.INP
- Dòng đầu tiên chứa hai số nguyên N, M
- Dòng thứ hai chứa các phần tử của dãy A[1..N]. M dòng cuối chứa các yêu cầu.
Dữ liệu ra: file MAXIJ.OUT gồm một số dòng tương ứng là kết quả của các yêu
cầu Q trong dữ liệu vào.
Ví dụ:
MAXIJ.INP
MAXIJ.OUT
53
5
54321
7
Q13
C37
Q24
Giới hạn: 1 N 100000; |Ai| 1000, M 100000
Ý tưởng
Đối với truy vấn 1 mỗi giá trị cần thay đổi vào thì ta cập nhật lên cây interval
tree
Đối với truy vấn 2 vì node gốc lưu giá trị lớn nhất toàn cây cho nên ta bắt đầu
từ node này và gọi đệ quy maxij(1,n,u,v,1); để lấy kết quả
CODE
uses crt, math;
const fi='MAXIJ.INP';
fo='MAXIJ.OUT';
maxn=trunc(1e5);
var
T:array[1..5*maxn] of longint;
ch:char;
m,n,i,u,v,res:longint;
6
Cấu trúc dữ liệu đặc biệt
f,g:text;
procedure
truyvan1(l,r,i,d:longint);{cap nhat mang t}
var mid:longint;
begin
if (ir) then exit;
if (i=L)and(j=R) then
begin
res:=max(res,t[d]);
exit;
end;
mid:=(L+R) div 2;
truyvan2(L,mid,i,min(mid,j),2*d);
truyvan2(mid+1,R,min(i,mid+1),j,2*d+1);
end;
{==========================================================}
begin
assign(f,fi);
reset(f);
assign(g,fo);
rewrite(g);
readln(f,n,m);
for i:=1 to n do
begin
read(f,v);
truyvan1(1,n,i,1);
end;
readln(f);
7
Cấu trúc dữ liệu đặc biệt
res:=low(longint);
for i:=1 to m do
begin
readln(f,ch,u,v);
case ch of
'Q':begin
truyvan2(1,n,u,v,1);
writeln(g,res);
res:=low(longint);
end;
'C':truyvan1(1,n,u,1);
end;
end;
close(f);
close(g);
end.
Bài 2
Cho một dãy gồm N phần tử, giá trị ban đầu mỗi phần tử bằng 0.
Cho m phép biến đổi, mỗi phép có dạng (u, v, k) tăng mỗi phần tử từ vị trí u đến
vị trí v lên k đơn vị.
Với q câu hỏi, mỗi câu có dạng (u, v): cho biết phần tử có giá trị lớn nhất trên
đoạn [u, v]
Dữ liệu vào: file QMAX.INP
- Dòng đầu tiên chứa hai số nguyên N, M
- m dòng tiếp theo, mỗi dòng chứa u, v, k là cho biết một phép biến đổi
Dòng thứ m+2 là q
- q dòng tiếp theo, mỗi dòng chứa u, v cho biết một phép biến đổi
Dữ liệu ra: file QMAX.OUT gồm q dòng tương ứng là kết quả của các yêu cầu
trong dữ liệu vào.
Ví dụ:
QMAX.INP
QMAX.OUT
62
3
132
463
1
34
Giới hạn: 1 N 100000; |Ai| 1000, M 100000
Nhận xét
8
Cấu trúc dữ liệu đặc biệt
Bài này không nên vận dụng máy móc nếu ta dùng kĩ thuật IT tức là ta cập
nhật trên đoạn [i, j] trước thì độ phức tạp của việc cập nhật O( mx ( v u 1) x log(n ) )
Cho nên ta dùng cách rãi sỏi hai đầu với m lần, mỗi lần
a[u] a[u]+k
a[v 1] a[v 1]-k
Tiếp theo : a[i]=a[i]+a[i-1] , với i 1..m
Như vậy độ phức tạp lúc này O(m+n)
Từ mảng A đó ta mới bắt đầu cập nhật lên cây thì độ phức tạp O(log(n))
Còn q câu hỏi thì ta vận dụng truy vấn trên cây IT bắt đầu truyvan(1,1,n,u,v)
sẽ có kết quả để trả lời cho từng câu hỏi của đề bài.
Lưu ý: Bài tập này có thể giải quyết bằng BIT.
Với bài này thì độ phức tạp O ((m+q) log n)
CODE
uses crt, math;
const fi='QMAX.INP';
fo='QMAX.OUT';
maxn=trunc(1e6);
var
T,A:array[0..maxn] of longint;
m,n,q:longint;
procedure modify(l,r,d:longint);
var mid:longint;
begin
if l=r then
begin
T[d]:=a[L];
exit;
end;
mid:=(l+r) div 2;
modify(l,mid,d*2);
modify(mid+1,r,d*2+1);
T[d]:=max(T[d*2],T[d*2+1]);
end;
{=================================================}
procedure find(l,r,u,v,d:longint; var GTLN:longint);
var mid,maxL,maxR:longint;
begin
if (v
Tmin[d]:=min(Tmin[d*2],Tmin[d*2+1]);
Tmax[d]:=max(Tmax[d*2],Tmax[d*2+1]);
end;
Truyvan thì đơn giản rồi ta vận dụng truy vấn cây IT là sẽ được kết quả theo
yêu cầu của bài.
14
Cấu trúc dữ liệu đặc biệt
Một số bài tập khác
http://vn.spoj.com/problems/QMAX3VN/
http://vn.spoj.com/problems/QMAX4/
http://vn.spoj.com/problems/LITES/
http://vn.spoj.com/problems/MARBLE/
.......
15
Cấu trúc dữ liệu đặc biệt
C. KẾT LUẬN
Interval tree là một trong những cấu trúc dữ liệu đặc biệt, nó giúp ta có thể
giải được nhiều bài toán trong thời gian cho phép. Độ phức tạp thông thường khi
làm việc với Interval là O(logN). Có hai thao tác quan trọng:
Cập nhật giá trị vào vị trí i hoặc trên một đoạn[i, j] rất nhanh chóng của một
dãy.
Khai thác trên dãy số (có số lượng phần tử lớn) trong một thời gian ngắn.
Trong thời gian ngắn vừa tìm hiểu và vừa viết chuyên đề này nên không thể
tránh khỏi thiếu sót mong sự góp ý của thầy cô và các em học sinh để chuyên đề
này hoàn thiện hơn.
16
Cấu trúc dữ liệu đặc biệt
D. TÀI LIỆU THAM KHẢO
1. Giải thuật và lập trình của thầy Lê Minh Hoàng
2. Bài tập trên Website:www.spoj
3. Một số vấn đề đáng chú ý trong môn tin học của thầy Phan Công Minh chủ
biên
4. Tài liệu ..... của thầy Trần Đỗ Hùng
17
- Xem thêm -