Tài liệu Bồi dưỡng học sinh giỏi tin học thpt chuyên đề interval tree(it)

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