Tài liệu Bồi dưỡng học sinh giỏi tin học thpt chuyên đề hiệu quả sử dụng cấu trúc interval tree

  • Số trang: 25 |
  • Loại file: PDF |
  • Lượt xem: 1285 |
  • Lượt tải: 0

Mô tả:

HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 HIỆU QUẢ SỬ DỤNG CẤU TRÚC INTERVAL TREE I.Đặt vấn đề Các bài toán trên dãy số đang xuất hiện nhiều trong các đề thi olympic tin học quốc gia và quốc tế, Có rất nhiều cấu trúc lưu trữ được sử dụng để xử lý đối với các bài toán dạng này, Theo tìm hiểu cá nhân tôi thì một trong các cấu trúc lưu trữ hiệu quả với các thao tác xử lý ít tốn thời gian hơn các cấu trúc khác đó là INTERVAL TREE (Cây đoạn). Cây đoạn là một 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. Chính vì vậy, Tôi viết chuyên đề này nhằm làm rõ mức độ hiệu quả khi sử dụng cấu trúc interval tree thông qua một số bài tập có thể áp dụng cấu trúc này để giải quyết. II.Nội dung 1.Lý thuyết nền tảng Cây phân đoạn là một cây, các nút của nó lưu thông tin của một đoạn xác định. Interval tree là một cây nhị phân mà mỗi nút không phải là lá đều có đúng 2 nút con. Nếu nút A lưu thông tin của đoạn từ i..j thì 2 nút con của nó, A1 và 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 của đoạn. Vì đầy là cây nhị phân, lại có đầy đủ 2 nút con, để đơn giản thì ta có thể biễu diễn cây chỉ bằng 1 mảng 1 chiều với ý nghĩa như sau: Nút 1 là nút gốc, nút k( nếu không phải là nút lá) thì có 2 con là các nút k*2 ( nút con trái) và k*2+1(nút con phải). Nút 1 sẽ lưu thông tin của đoạn 1..n ( với n là độ dài của dãy số). Vậy nút 2 sẽ 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. Tương tự theo định nghĩa thì ta có thể biết được nút thứ k sẽ lưu thông tin của một đoạn xác định nào đó. Sau đây là hình ảnh 1 cây INTERVAL TREE với n =7: 1 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Có một vấn đề là với 1 đoạn n phần tử thì mảng biễu diễn cây sẽ có bao nhiêu phẩn tử là đủ, người ta đã chứng minh được cây interval tree chỉ cần tối đa là 4*n-5 phần tử, vì vậy khi khai báo 1 cây interval tree ta thường khai báo 1 mảng 1..4*n. Trên interval tree có 2 thao tác cần xử lý: 1 là cập nhật thay đổi cho đoạn i..j và 2 là lấy thông tin cần có của đoạn i..j, những mỗi nút của interval trê chỉ lưu những đoạn xác định, vì vậy 2 thao tác này có thể cần tác động đến nhiều nút. Để dễ hình dung, ta lấy 1 ví dụ cụ thể: Cho 1 dãy n phần tử (n<= 10^5), ban đầu mỗi phần tử có giá 0. Có q<=10^5 truy vấn, mỗi truy vấn là 1 trong 2 thao tác sau: 1 là gán giá trị v(v>0) cho phần tử ở vị trí i, 2 là tìm giá trị lớn nhất trong đoạn i..j bất kì. Cách đơn giản nhất là ta có 1 mảng A[1..100000], với thao tác 1 thì gán A[i]=v, thao tác 2 thì cho 1 vòng for từ i đến j để tìm max, nhưng cách này trong trường hợp có nhiều truy vấn thứ thì sẽ chạy rất lâu, trừng hợp xấu nhất là n*q. Dễ thấy cách này không thể chạy trong thời gian cho phép. Cách dùng interval như sau:  Với truy vấn 1, ta sẽ cập nhật là kết quả max cho tất cả các đoạn mà chứa phần tử thứ i, những đoạn còn lại thì không làm gì cả vì không ảnh hưởng đến.  Với đoạn truy vấn 2, ta cần tìm kết quả max trong số tất cả những đoạn nằm gọn tron i..j, tức là những đoạn có điểm đầu >=i và điểm cuối <=j.  Gọi T[1..400000] of longint là mảng để lưu trữ cây interval tree. T[i] là giá trị lớn nhất trong đoạn mà nút k lưu giữ thông tin. Khi gặp truy vấn 1, ta làm như trong thủ tục sau: 2 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Procedure truyvan1(k,l,r,i:longint); Var m: longint; Begin 1. if (l<=i) or (r>i) then exit; 2. if (l=r) then begin T[k]:= v; exit; end; 3. m:=(l+r) div 2; 4. truyvan1(k*2,l,m,i); 5. truyvan1(k*2+1,m+1,r,i); 6. T[k]:=max(T[k*2],T[k*2+1]); end; Ta sẽ phân tích thủ tục truyvan1: - Thủ tục này có các tham số k,l,r,i với ý nghĩa: l và r là điểm đầu và điểm cuối của đoạn mà nút k lưu trữ thông tin, i chính là phần tử cần gán giá trị v. - Trong thủ tục có 1 biến m để xác định phần tử nằm giữa đoạn l..r. - Câu lệnh 1 có ý nghĩa là ta sẽ bỏ qua không làm gì với các đoạn không chứa phần tử thứ i (l>i hoặc r T[k]:=max(T[k*2],T[k*2+1]) Khi gọi thủ tục truy vấn 1, ta sẽ gọi từ nút gốc, tức là gọi truyvan1(l,l,n,i); Vậy là đã xong yêu cầu thứ nhất, nhưng cái ta cần để xem chương trình có hoạt động tốt hay không lại là kết quả của yêu cầu thứ 2, vì vậy thủ tục truyvan1 là để giúp thủ tục truyvan2 sau đây để tìm được kết quả với đoạn i..j bất kì, 3 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Procedure truyvan2(k,l,r,i,j:longint); Var m: longint Begin 1. if (l>j) or (r= r) then Begin res:=max(res,T[k]);exit; End; 3. m:=(l+r) div 2; 4. truyvan2(k*2,l,m,I,j); 5. truyvan2(k*2+1,m+1,r,i,j); end; Phân tích: Thủ tục truy vấn 2 này có các tham số với ý nghĩa như thủ tục 1, có thêm số j vì cần lấy kết quả trên đoạn i..j. Mỗi đoạn l..r sẽ có 3 khả năng với đoạn i..j. a: l..r không giao i..j, trường hợp này bỏ qua không làm gì cả( câu lệnh 1). b: l..r nằm gọn trong i..j, trường hợp này thì ta chỉ cần tối ưu kết quả khi so sánh với T[k] vì: Ta đã xác định được phần tử lớn nhất trong đoạn l..r nhờ thử tục 1, và do l..r nằm gọn trong i..j nên không cần đi vào 2 nút con của nó (câu lệnh 2). c: l..r không nằm trong đoạn i..j nhưng có 1 phần giao với i..j, trường hợp này thì ta sẽ đi vào 2 nút con của nó để lấy kết quả, đến khi nào gặp phải 2 trường hợp đầu ( câu lệnh 4 và 5). Suy nghĩ kĩ sẽ thấy thủ tục truy vấn 2 không bỏ sót cũng như tính thừa phần tử nào ngoài đoạn i..j. Khi gọi thủ tục truyvan2 ta cũng gọi từ nút gốc truyvan2(l,l,n,i,j). Sau thủ tục thì in ra res là kết quả cần tìm. Người ta cũng chứng minh được rằng, độ phức tạp của mỗi thủ tục truyvan1 và truyvan2 không quá log(n). Vì vậy thuật toán dùng interval tree cho bài toán này có độ phức tạp không quá q*log(n)=10^5*log(10^5). Có thể chạy trong thời gian cho phép. Đây là 1 trong những ví dụ cơ bản nhất về interval tree, hi vọng các bạn đã có thể hiểu và cài đặt nó. Trong khi nghiên cứu về các bài tập sau đây, ta sẽ tìm hiểu 1 vài kiểu sử dụng interval tree khác. Đây cũng là 1 trong những cấu trúc dữ liệu thường găp được sử dụng trong các kì thi Olympic Tin học trên thế giới. Các bài tập này sẽ được trình bày trong phần bài tập ứng dụng. 4 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 2.Bài tập ứng dụng Bài toán 1: Dãy con tăng dài nhất Cho dãy số a1 , a2 ,..., an . Hãy tìm dãy con (không nhất thiết gồm các phần tử liên tiếp) tăng dài nhất. Đây là bài toán qui hoạch động quen thuộc: Đặt f[i] là độ dài dãy con tăng dài nhất kết thúc tại ai. Ta có công thức qui hoạch động sau: f [i]  max {f [k ]: k  i, ak  ai }  1 (1) Có nhiều cách để tính toán (1) trong thời gian O(log n). Một trong những cách như vậy là sử dụng tìm kiếm nhị phân. Ở đây, chúng ta tiếp cận theo một cách khác: Trước tiên giả thiết rằng ai 1,2,..., n với i=1,2,...,n. Bất đẳng thức ak  ai có thể viết dưới dạng ak  [1... ai 1] . Do đó việc tính (1) có thể qui về việc tính lần lượt f[1], f[2], .... và với mỗi i=1,2,...,n thì f[i] được tính bằng cách lấy giá trị lớn nhất của các giá trị f đã được tính có điểm cuối thuộc [1...ai-1] (mỗi lần có được giá trị f[i] ta ghi nhận nó vào vị trí ai[1...n]) và ta có thể sử dụng IT để thực hiện các truy vấn tìm max này). Dưới đây là mã chương trình viết bằng IT: void update(int r,int k,int l,int u,int v,int val) { if (vl) return; if (u<=k && l<=v) {dt[r]+=val; return;} int g=(k+l)/2; dt[2*r]+=dt[r]; dt[2*r+1]+=dt[r]; dt[r]=0; update(2*r,k,g,u,v,val); update(2*r+1,g+1,l,u,v,val); it[r]=max(it[2*r]+dt[2*r],it[2*r+1]+dt[2*r+1]); } 5 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 int get(int r,int k,int u,int v) { if (vl) return -INF; // INF là giá trị đủ lớn if (u<=k && l<=v) return it[r]+dt[r]; int g=(k+l)/2; dt[2*r]+=dt[r]; dt[2*r+1]+=dt[r]; dt[r]=0; int t1=get(2*r,k,g,u,v); int t2=get(2*r+1,g+1,l,u,v); it[r]=max(it[2*r]+dt[2*r],it[2*r+1]+dt[2*r+1]); return max(t1,t2); } for(int i=1;i<=n;i++) { f[i]=get(1,1,n,1,a[i]-1)+1; update(1,1,n,a[i],a[i],f[i]); } Độ phức tạp là O(n log n) Tuy nhiên, để có thể sử dụng IT như trên chúng ta đã phải giả thiết rằng ai  [1... n] . Nếu như không có điều kiện trên thì sao? Trong trường hợp này chúng ta phải sử dụng một kỹ thuật thường được gọi là rời rạc hóa: Cho tương ứng dãy a1 , a2 ,..., an với dãy b1 , b2 ,..., bn sao cho thỏa mãn:  Nếu ai  a j , ai  a j , ai  a j thì bi  bj , bi  bj , bi  bj  bi  [1...n] 6 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Dễ thấy việc tìm dãy con tăng dài nhất trên dãy a1 , a2 ,..., an hoàn toàn giống như việc tìm dãy con tăng dài nhất trên dãy b1 , b2 ,..., bn . Đoạn mã dưới đây làm công việc này: for(int i=1;i<=n;i++) x[i]=a[i]; sort(x+1,x+n+1); for(int i=1;i<=n;i++) b[i]=lower_bound(x+1,x+n+1,a[i])-x; Nếu code bằng Pascal, trước tiên ta sắp xếp lại mảng A theo chỉ số:a[id[1]] ≤a[id[2]]≤...a[id[n]]. Sau đó thực hiện đoạn mã sau: m=1; b[id[1]]:=1; for i:=2 to n do begin if a[id[i]]>a[id[i-1]] then inc(m); b[id[i]]:=m; end; Tất nhiên, cách tiếp cận trên để giải bài toán 1 phức tạp hơn cách tiếp cận sử dụng tìm kiếm nhị phân truyền thống. Tuy vậy qua ví dụ trên có thể tổng kết một số điều khi sử dụng IT:  Nói chung, IT được xây dựng trên miền giá trị của mảng. Luôn co miền giá trị vào một khoảng hữu hạn đủ nhỏ [1...m] bằng kỹ thuật rời rạc hóa (nếu cần thiết)  Viết các biểu thức so sánh thành các biểu thức tập hợp: a  x  b được viết thành x  [a, b] để xây dựng được các truy vấn max, min, sum trên một khoảng. Điều này là quan trọng vì nó thể hiện đặc trưng của IT. Bài tập 2: Tính diện tích hình chữ nhật phủ Cho N hình chữ nhật có tọa độ nguyên nằm trên mặt phẳng tọa độ và có các cạnh song song với các trục. Mỗi hình chữ nhật được cho bởi tọa độ đỉnh trái trên và đỉnh phải dưới. Yêu cầu: Hãy tính diện tích mà tất cả các hình chữ nhật này phủ lên. Input: COVER.INP   Dòng đầu là số N – số hình chữ nhật (1 ≤ N ≤ 10000) N dòng tiếp theo, dòng thứ i gồm 4 số Xi, Yi, Ai, Bi thể hiện tọa độ đỉnh trái trên và đỉnh phải dưới của hình chữ nhật thứ i (-20000 ≤ Xi, Yi, Ai, Bi ≤ 20000) 7 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Output: COVER.OUT  Gồm một dòng duy nhất là đáp số của bài toán Thời gian chạy: 0.5s Ví dụ: COVER.INP COVER.OUT 5 28 -2 2 1 0 4 2 6 0 -1 5 3 2 4 6 6 5 2 3 5 1 Minh họa: 8 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Hướng dẫn: Để tiện cho việc phân tích bài toán, chúng ta sẽ gọi hoành độ của các đỉnh hình chữ nhật là H1, H2, …, H2*N được sắp xếp theo chiều tăng; tung độ của các đỉnh hình chữ nhật là T1, T2, …, T2*N (giả sử các tung độ được liệt kê theo chiều tăng - ở đây chú ý rằng: chỉ có hoành độ được sắp xếp tăng, còn tung độ là do chúng ta quy ước). Cách làm thông thường là sắp xếp H theo chiều tăng như đã giả sử ở trên, sau đó tính diện tích ở từng khe H1H2, H2H3, …, H2*N2 1H2*N. Như vậy, độ phức tạp của thuật toán của chúng ta là O(N ), thời gian là T(N(log2N + N)), khó có thể đáp ứng thời gian chạy là 1s. Để cho tiện, tất cả dữ liệu của chúng ta đều coi như sắp xếp bằng Quick Sort. Trong hoàn cảnh đó, rất may mắn, chúng có một cấu trúc dữ liệu đặc biệt khác có thể thực hiện được điều này với độ phức tạp O(Nlog2N) và thời gian chạy là T(2Nlog2N). Đó là dùng Interval Tree, bản chất của Interval hết sức đơn giản, chúng ta sẽ xét rõ hơn qua phân tích chi tiết bài toán này. Thuật toán của chúng ta về bản chất cũng giống với thuật toán vừa đề cập:  Sắp xếp các hoành độ tăng dần.  Tính diện tích che phủ từng khe H1H2, H2H3, …, H2*N-1H2*N của hoành độ, lấy tổng, ta được đáp số của bài toán. Trước hết, ta gán cho mỗi hoành độ đã được sắp xếp một nhãn, nhãn đó sẽ gồm Low, High lưu lại tung độ của hình chữ nhật chứa hoành độ đó và nhãn Open. Open sẽ chứa giá trị true nếu đó là đỉnh trên trái của hình chữ nhật, false nếu đó là đỉnh dưới phải của hình chữ nhật. Với đề bài, ta sẽ có các hoành độ được gán nhãn (sau khi đã sắp xếp) như sau: H[1] = -2; Label[1].Low = 0; Label[1].High = 2; Label[1].Open = true; H[2] = -1; Label[2].Low = 2; Label[2].High = 5; Label[2].Open = true; ... Tiếp theo ta sẽ xây dựng một cây nhị cây nhị phân đầy đủ, mỗi đỉnh sẽ tượng trung cho số hình chữ nhật che phủ trên đoạn [A, B] thuộc tung độ, mỗi đỉnh gồm có 2 phần Number và Cover với ý nghĩa: 1) Number: số lượng hình chữ nhật che phủ toàn bộ [A, B] 2) Cover: tổng số đoạn tung độ bị che phủ trên đoạn [A, B] 9 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Đỉnh 1 của cây có đoạn [A, B] tương ứng là [Min, Max] (với Min, Max tương ứng là tung độ nhỏ nhất và lớn nhất trong số các hình chữ nhật); đỉnh 2 có đoạn tương ứng [A, B] là [1, Max div 2]; đỉnh 3 là [Max div 2, Max],… tạo thành một cây nhị phân đầy đủ. Đơn giản hơn, với mỗi đỉnh chứa thông tin về đoạn [A, B], hai nút con tương ứng của nó sẽ lưu trữ thông tin về đoạn [A, (A+B) div 2] và [(A+B) div 2, B]. Sở dĩ đỉnh con thứ hai không xét từ [(A+B) div 2 + 1, B] bởi lẽ chúng ta đang xét theo tung độ chứ không phải là xét theo độ dài đoạn thẳng, nếu xét như vậy ta sẽ không bị sót đoạn [(A+B) div 2, (A+B) div 2 + 1]. Quá trình xây dựng cây nhị phân sẽ được đồng nhất với quá trình tính diện tích, có nghĩa là với mỗi khe H1H2, H2H3, …, H2*N-1H2*N chúng ta sẽ xây dựng cây nhị phân tương ứng với hình chữ nhật đang xét. Lưu ý rằng “hình chữ nhật đang xét” ở đây nói về hình chữ nhật liên quan đến các hoành độ H sau khi đã sắp xếp, bởi như đã nói ở trên, H được gán nhãn để đại diện cho một đỉnh của hình chữ nhật. Giả sử rằng chúng ta đang xét đến khe thứ i và i-1, đỉnh k của cây mang đoạn [A, B], có thể xảy ra 2 trường hợp sau: 1. Đỉnh H[i] đang xét là đỉnh trái trên của hình chữ nhật: Có 3 khả năng xảy ra:  Nếu hình chữ nhật che phủ đoạn [A, B], tức là (Low ≤ A) and (B ≤ High): 10 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Khi đó số hình chữ nhật bị che phủ phải tăng lên 1 và tổng số che phủ chính bằng High – Low. Ta không cần phải xét đến các nút con của nó.  Nếu hình chữ nhật nằm hoàn toàn ngoài đoạn [A, B], tức là (High ≤ A) or (B ≤ Low): (vì chúng ta đang xét đến tung độ nên phải thêm “=” bởi nếu có “=” thì số phần bị che phủ cũng không tăng lên): Khi đó, chắc chắn hình chữ nhật cũng không che phủ lên các nút con của nó, ta không phải làm gì cả.  Nếu hình chữ nhật giao với đoạn [A, B], tức là trường hợp còn lại: Ta xét đến các nút con của nút k. Nếu như số hình chữ nhật bao phủ lên k là 0 chứng tỏ tổng số che phủ của k bằng tổng số che phủ của các nút con của nó. Procedure Open_True(A, B, k, Low, High); Begin if A + 1 >= B then {Xét đến nút lá – trường hợp đặc biệt} begin if (Low <= A) and (B <= High) then Cover[k] := 1 else Cover[k] := 0; exit; end; if (Low <= A) and (B <= High) then {Che phủ [A, B]} begin Number[k] := Number[k] + 1; Cover[k] := B – A; exit; end; {Nằm ngoài} {Giao nhau} if (High <= A) or (B <= Low) then exit; {Xét nút con trái} 11 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Open_True(A, (A+B) div 2, 2*k, Low, High); {Xét nút con phải} Open_True((A+B) div 2, A, 2*k+1, Low, High); if Number[k] = 0 then Cover[k] := Cover[2*k] + Cover[2*k+1]; End; 2. Đỉnh H[i] đang xét là đỉnh phải dưới của hình chữ nhật: Có 3 khả năng xảy ra:  Nếu hình chữ nhật che phủ đoạn [A, B], tức là (Low ≤ A) and (B ≤ High): Khi đó số hình chữ nhật bị che phủ phải giảm lên 1. Nếu như không còn hình chữ nhật nào che phủ nó thì tổng số che phủ bằng tổng số che phủ của các nút con của nó. Ta không cần phải xét đến các nút con.  Nếu hình chữ nhật nằm hoàn toàn ngoài đoạn [A, B], tức là (High ≤ A) or (B ≤ Low): (vì chúng ta đang xét đến tung độ nên phải thêm “=” bởi nếu có “=” thì số phần bị che phủ cũng không tăng lên): Khi đó, chắc chắn hình chữ nhật cũng không che phủ lên các nút con của k, ta không phải làm gì cả.  Nếu hình chữ nhật giao với đoạn [A, B], tức là trường hợp còn lại: Ta xét đến các nút con của nút k. Nếu như số hình chữ nhật bao phủ lên k là 0 chứng tỏ tổng số che phủ của k bằng tổng số che phủ của các nút con của nó. Procedure Open_False(A, B, k, Low, High); Begin if A + 1 >= B then {Xét đến nút lá – trường hợp đặc biệt} begin if (Low <= A) and (B <= High) then begin Number[k] := Number[k] - 1; if Cover[k] = 0 then 12 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Cover[k] := Cover[2*k] + Cover[2*k+1]; end; exit; end; if (Low <= A) and (B <= High) then {Che phủ [A, B]} begin Number[k] := Number[k] - 1; if Cover[k] = 0 then Cover[k] := Cover[2*k] + Cover[2*k+1]; exit; end; if (High <= A) or (B <= Low) then exit; {Nằm ngoài} {Giao nhau} Open_False(A, (A+B) div 2, 2*k, Low, High); {Xét nút con trái} Open_False((A+B) div 2, A, 2*k+1, Low, High); {Xét nút con phải} if Number[k] = 0 then Cover[k] := Cover[2*k] + Cover[2*k+1]; End; Để tiện cho việc lưu trữ, Interval Tree của chúng ta sẽ được lưu trữ bằng mảng, đỉnh i có 2 con là 2*i và 2*i+1. Phần khó nhất là việc xây dựng cây đã xong, chương trình xử lý của chúng ta sẽ bao gồm sắp xếp theo H và xét các khe H1H2, H2H3, …, H2*N-1 H2*N : 13 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Procedure Solve; begin Sort; {Sắp xếp dãy} Open_True(Min, Max, 1, Label[1].Low, Label[1].High); Area := 0; for i := 2 to 2*n do begin Area := Area + Cover[1] * (H[i] – H[i-1]); {Tính diện tích} if Label[i].Open then Open_True(Min, Max, 1, Label[i].Low, Label[i].High) else Open_False(Min, Max, 1, Label[i].Low,Label[i].High); end; end; Chú ý:  Một số bạn sẽ cho rằng nếu như tại một hoành độ có nhiều đỉnh đóng hoặc nhiều đỉnh mở thì sao? Câu trả lời là không sao cả, bởi lẽ lúc đó H[i] – H[i-1] sẽ bằng 0 và diện tích sẽ không được tính vào Area. Thêm nữa, các đỉnh có chung hoành độ sẽ được mở hoặc đóng cho đến hết rồi mới được thực sự tính vào diện tích.  Cần phân biệt Number là số hình chữ nhật phủ lên đoạn [A, B] trong một đỉnh của cây chứ không phải số hình chữ nhật được đoạn [A, B] phủ. Sở dĩ chúng ta cần đến Number bởi nếu có một hình chữ nhật phủ kín đoạn [A, B]  Nhiều bạn mới đọc sẽ thắc mắc: Chúng ta đang xét đến các khe, làm sao có thể xét 14 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 được hết các hình chữ nhật có chung hoành độ được? Câu trả lời nằm ở chú ý thứ nhất: tất cả các hình chữ nhật có chung hoành độ, bất kể là đỉnh trên trái hay dưới phải đều được xét hết trước khi diện tích được cộng chính thức vào tổng. Loại cây mà chúng ta vừa sử dụng được gọi là Interval Tree. Vậy, Interval Tree là gì? Có thể nói vắn tắt lại rằng Interval Tree thực chất là một loại cây nhị phân đầy đủ với mỗi đỉnh chứa các thông tin về một đoạn [A, B] xác định. 2 con của nó chứa thông tin về đoạn [A, (A+B) div 2] và [(A+B) div 2 + 1, B]. Tùy theo mục đích sử dụng Interval Tree mà chúng ta có các loại Interval Tree khác nhau. Mấu chốt của bài toán là chúng ta nhận ra được tầm quan trọng của việc xác định đoạn mở và đoạn đóng trên một trục nhất định (ở bài toán trên chúng ta chọn trục tung). Theo cách giải thông thường, chúng ta phải lặp để xác định sự chồng chéo nhau của các đoạn nguyên, độ phức tạp của thuật giải thông thường là rất cao. Nhưng giờ đây với Interval Tree, độ phức tạp chỉ là O(log2N), với trường hợp xấu nhất. Bài tập 3: Xếp hàng(NKLINEUP) Hàng ngày khi lấy sữa, N con bò của bác John (1 N 50000) luôn xếp hàng theo thứ tự không đổi. Một hôm bác John quyết định tổ chức một trò chơi cho một số con bò. Để đơn giản, bác John sẽ chọn ra một đoạn liên tiếp các con bò để tham dự trò chơi. Tuy nhiên để trò chơi diễn ra vui vẻ, các con bò phải không quá chênh lệch về chiều cao. Bác John đã chuẩn bị một số danh sách gồm Q (1 Q 200000) đoạn các con bò và chiều cao của chúng (trong phạm vi [1,1000000]),. Với mỗi đoạn, bác John muốn xác định chênh lệch chiều cao giữ con bò thấp nhất và cao nhất. Bạn hãy giúp bác John thực hiện công việc này! Dữ liệu  Dòng đầu tiên chứ 2 số nguyên N và Q.  Dòng thứ i trong số N dòng sau chứa 1 số nguyên duy nhất, là độ cao của con bò thứ i.  Dòng thứ i trong số Q dòng tiếp theo chứa 2 số nguyên A,B (1 A B N), cho biết đoạn các con bò từ A đến B. Kết quả Gồm Q dòng, mỗi dòng chứa 1 số nguyên, là chênh lệch chiều cao giữ con bò thấp nhất và cao nhất thuộc đoạn tương ứng. 15 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Ví dụ Dữ liệu: 63 1 7 3 4 2 5 15 46 22 Kết quả 6 3 0 Thuật toán: Đây là 1 bài toán xử lí trên dãy số và cần truy cập đến những đoạn A..B bất kì trong dãy, vì vậy interval tree là 1 trong những lựa chọn không tồi. Bài này chúng ta có 1 điều may mắn là không cần phải cập nhật lại chiều cao của con bò, vì vậy thông tin trong cây interval tree là cố định và ta sẽ tạo cây interval trên dựa trên mảng chiều cao của các con bò. Mỗi đoạn thì ta cần in ra chênh lệch độ cao con bò cao nhất và con bò thấp nhất, vì vậy chúng ta cần tìm đực giá trị lớn nhất và giá trị nhỏ nhất trong các phần tử từ A đến B. Ta có thể dùng 1 cây interval tree với mỗi nút lưu 2 thông tin, giá trị lớn nhất và giá trị nhỏ nhất trong đoạn mà nó biểu diễn, cũng có thể dùng 2 cây interval tree, 1 cây dùng để lưu giá trị lớn nhất, cây còn lại là giá trị nhỏ nhất. Ở đây ta gọi 2 cây này là maxd và mind phần tạo ta có thể làm rất đơn giản dựa trên ý tưởng sau: Nếu l=r thì Maxd[k]=Mind[k]=A[l]; Nếu không thì Maxd[k]=max(Maxd[k*2], Maxd[k*2+1]) và Mind[k]:=min(Mind[k*2],Mind[k*2+1]; 16 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Khi muốn tìm kết quả thì dựa vào bảng Maxd để tìm GTLN trên đoạn A..B, dùng mảng Mind để tìm GTNN trên đoạn A..B, việc này làm tương tự như trong ví dụ của bài viết giới thiệu về interval tree phía trên. Chú ý là khi tìm max hay tìm min ta đều phải đi đến những nút giống nhau( do đi đến những nút nào thì chỉ phụ thuộc A và B) nên mỗi lần tìm chỉ cần gọi chung 1 thủ tục. Bài tập 4: Giá trị lớn nhất(QM A X) Cho một dãy gồm n phần tử có giá trị ban đầu 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ị. Cho 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 thuộc đoạn [u, v] Giới hạn  n, m, q <= 50000  k>0  Giá trị của một phần tử luôn không vượt quá 231-1 Input  Dòng 1: n, m  m dòng tiếp theo, mỗi dòng chứa u, v, k cho biết một phép biến đổi  Dòng thứ m+2: p  p dòng tiếp theo, mỗi dòng chứa u, v cho biết một phép biến đổi Output  Gồm p dòng chứa kết quả tương ứng cho từng câu hỏi. Example Input: 62 132 463 1 34 Output: 3 17 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Thuật toán: Bài này thì ta có m phép biến đổi tăng dãy trước rồi mới yêu cầu tìm giá trị lớn nhất trong các đoạn chứ không phải xen kẽ nhau, vì vậy ta sẽ tìm cách xây dựng dãy số sau m phép biến đổi. Khi có được mảng giá trị sau m phép biến đổi, công việc còn lại của ta là tạo 1 cây interval tree với mỗi nút lưu giá trị lớn nhất của đoạn mà nó quản lí trong khi các phần tử của mảng đã xác định, với mối truy vấn tìm GTLN thì ta có thể làm không mấy khó khăn. Vấn đề bây giờ là xây dựng dãy số sau m phép biến đổi. Ta có thể sử dụng 1 kĩ thuật đơn giản những rất hiệu quả như sau. Giả sử mảng ta cần có là mảng A[0..n+1], lúc đầu A[i]=0 với mọi i. Mỗi yêu cầu u,v,k tức là tăng các phần tử từ vị trí u đến vị trí v lên k đơn vị, ta làm như sau: A[u]:=A[u]+k; A[v+1]:=A[v+1]-k; Sau khi đọc xong m phép biến đổi và làm như trên, cuối cùng là tính mảng A: For i:=1 to n do A[i]:=A[i]+A[i-1]; Các bạn có thể tự chứng minh tính đúng đắn hay có thể viết đoạn chương trình này ra và kiểm nghiệm lại. Như vậy ta đã có thể giải quyết trọn vẹn bài toán. Bài tập 5: Giá trị lớn nhất ver2(QMAX2) Giống bài "Giá trị lớn nhất" ở trên. Input - n: số phần tử của dãy (n <= 50000). - m: số lượng biến đổi và câu hỏi (m <= 100000). +) biến đổi có dạng: 0 x y value +) câu hỏi có dạng : 1 x y. Output Ghi ra trả lời cho lần lượt từng câu hỏi. Example Input: 63 0133 18 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 0464 116 Output: 4 Thuật toán: Bài này khác bài QMAX ở trên là các phép biến đổi và các câu hỏi xen kẽ nhau, vì vậy ta không thể tạo trước 1 cây interval được. Để giải quyết bài toán này, ta cần phải thực hiện cập nhật cũng như lấy kết quả xen kẽ nhau. Nhưng ở đây thì các công việc này không hề đơn giản. Vừa có được kết quả, ta cũng cần phải đảm bảo 2 công việc này không được có độ phức tạp vượt quá log(n). Để làm bài này, ta gọi F[k] là giá trị lớn nhất trong đoạn mà nút k quản lí, trong lúc cập nhật, muốn đảm bảo thủ tục này không vượt quá log(n) thì khi đi đến 1 nút mà nằm gọn trong đoạn x..y thì ta không được đi vào các nút con của nó nữa( nếu không sẽ đi đến tất cả các đoạn có trong đoạn x..y và độ phức tạp tỷ lệ với n). Nếu như vậy, ta cần có 1 mảng phụ T để lưu lại giá trị cần tăng lên cho tất cả các phần tử của đoạn này, khi ta truy vấn đến 1 nút k đồng thời ta tăng T[k] lên cho T[k*2], T[k*2+1] và F[k]. (do T[k] là giá trị cần tăng lên cho tất cả những phần tử của đoạn nút k quản lí, nên các nút con của nó cũng phải tăng lên T[k]). Sau khi đã cập nhật cho mảng F và các nút con, ta gán lại T[k]=0 để tránh trường hợp cộng lại nhiều lần. Nếu đã đến đoạn nằm gọn trong đoạn x..y thì ta tăng mỗi biến F[k], T[k*2], T[k*2+1] lên v. Khi muốn lấy kết quả, ta vẫn làm như bài QMAX, nhưng đến mỗi nút con, ta vẫn cần thực hiện tăng giá trị T[k] cho T[k*2], T[k*2+1] và F[k] để lấy được kết quả. Tức là khi đến được 1 nút nào đó( trong bất kì thao tác nào, cập nhật hay lấy kết quả) thì đều thực hiện như vậy. điều này đảm bảo là ta có thể lấy được giá trị chính xác, đây là kiểu cây IT có thông tin truyền từ nút cha xuống nút con. Các bạn có thể tham khảo chương trình để thấy rõ hơn. Bài tập 6: Bật đèn(LITES) Bác John giữ cho đàn bò thông minh bằng cách để chúng chơi các đồ chơi phát triển trí tuệ. Một trong các trò chơi là các ngọn đèn trong chuồng. Mỗi trong số N (2 <= N <= 100,000) con bò được đánh số từ 1..N có treo một ngọn đèn màu. Vào đầu buổi tối, tất cả đèn đều tắt. Đàn bò điều khiển các ngọn đèn bằng N công tắc; bấm công tắc i đổi trạng thái của đèn i từ tắt sang bật hoặc ngược lại. 19 HIỆU QUẢ S Ử DỤNG CẤU TRÚC INTERVAL TREE 08/2015 Đàn bò đọc và thực thi một danh sách gồm M (1 <= M <= 100,000) thao tác mô tả bởi một trong hai số nguyên (0 <= thao tác <= 1). Thao tác thứ nhất (mô tả bởi số 0) theo sau bởi hai số nguyên S_i và E_i (1 <= S_i <= E_i <= N) cho biết công tắc đầu và công tắc cuối. Đàn bò sẽ bấm mỗi công tắc từ S_i đến E_i đúng một lần. Thao tác thứ hai (mô tả bởi số 1) yêu cầu đàn bò đến xem có bao nhiêu ngọn đèn giữa S_i và E_i (1<= S_i <= E_i <= N) đang bật. Hãy giúp bác John đảm bảo rằng đàn bò trả lời đúng bằng cách xử lý danh sách và trả về các kết quả đúng. Dữ liệu * Dòng 1: Hai số nguyên cách nhau bởi khoảng trắng: N và M * Dòng 2..M+1: Mỗi dòng chứa một thao tác với ba số nguyên cách nhau bởi khoảng trắng: thao tác, S_i, và E_i Kết quả * Dòng 1..số truy vấn: Với mỗi truy vấn, in ra kết quả là một số nguyên trên một dòng. Ví dụ Dữ liệu: 45 012 024 123 024 114 Kết quả: 1 2 Thuật toán: Ta có thể sử dụng INTERVAL TREE để làm như sau: Bài này có tư tưởng khá giống với bài QMAX2, thông tin được truyền từ nút cha xuống nút con bất cứ khi nào có thể. Ta có 1 mảng B kiểu logic, B[i]=true nghĩa là những đèn trong đoạn mà nút thứ i quản lí cần thay đổi trạng thái. Khi đến 1 nút, nếu b[i]=true thì cần thay đổi trạng thái của B[i*2] và B[i*2+1] đồng thời gán lại B[i]=false( đã thực hiện thay đổi rồi thì phải gán lại false), nếu gọi mảng sl[i] là số lượng đèn đang bật trong đoạn do nút i quản lí thì nếu gặp b[i]=true phải 20
- Xem thêm -