Tài liệu Bồi dưỡng học sinh giỏi tin học thpt chuyên đề cây quản lý đoạn

HỘI CÁC TRƯỜNG THPT CHUYÊN KHU VỰC DUYÊN HẢI VÀ ĐỒNG BẰNG BẮC BỘ ….…. HỘI THẢO LẦN THỨ VIII CHUYÊN ĐỀ CÂY QUẢN LÝ ĐOẠN MÔN: TIN HỌC TÁC GIẢ: TRẦN VĂN THUẬN ĐƠN VỊ: TRƯỜNG THPT CHUYÊN LÊ KHIẾT-QUẢNG NGÃI 1 11/2015 Hải Phòng, CÂY QUẢN LÝ ĐOẠN Segment trees là một cấu trúc dữ liệu ban đầu được thiết kế cho các ứng dụng hình học. Cấu trúc này khá phức tạp và được sử dụng để trả lời nhiều loại truy vấn khó. Segment trees thường được so sánh với interval trees là một dạng cấu trúc dữ liệu khác cũng cung cấp các chức năng tương đương. Trong mục này, ta đơn giản hóa cấu trúc segment trees để giải quyết bài toán truy vấn phạm vi. Điều này làm cho cây quản lý đoạn chỉ giống với segment trees ở hình ảnh biểu diễn còn các thuộc tính và phương thức trở nên đơn giản và “yếu” hơn nhiều so với cấu trúc nguyên thủy, theo nghĩa không trả lời được những truy vấn khó như cấu trúc nguyên thủy. Trên các diễn đàn thảo luận về thuật toán, đôi khi tên gọi interval trees hoặc segment trees vẫn được dùng để gọi tên cấu trúc này. Các bài giảng thuật toán cũng chỉ dùng tên gọi interval trees và segment trees để đề cập tới hai cấu trúc dữ liệu trong hình học tính toán. Cấu trúc cây quản lý đoạn, chỉ là một hạn chế của interval trees hay segment trees trong trường hợp cụ thể. Cấu trúc cây quản lý đoạn cung cấp một cách quản lý mới thông qua các đoạn sơ cấp, ngoài ra việc cài đặt dễ dàng cũng là một ưu điểm của cấu trúc dữ liệu này. 1. Cấu trúc cây quản lý đoạn Cây quản lý đoạn là một cây nhị phân đầy đủ (full binary trees) có cấu trúc như sau: - Mỗi nút quản lý một dãy các đối tượng liên tiếp, trong nút chứa thông tin tổng hợp từ các đối tượng mà nó quản lý. - Nút gốc quản lý các đối tượng từ 1 tới n. - Nếu một nút quản lý dãy các đối tượng từ l tới r (lr) then exit; {nếu k là nút lá} if ( l = r) then begin T[k] := a[l] exit; End; {nếu k không là nút lá} Build(2*k, l, (l+r) div 2); Build(2*k + 1, (l+r) div 2 + 1, r); 4 T[k] := T[2 * k] + T[2 * k + 1]; end; Thủ tục khởi tạo cây quản lý đoạn sẽ được thực hiện bằng lời gọi Build(1,1,n). Cập nhật thông tin cho đoạn Mỗi khi có sự thay đổi giá trị phần tử ta cần phải cập nhật lại cây. Khi một phần tử ai bị thay đổi, ta nhảy tới nút k là nút lá trực tiếp quản lý ai, thay T[k] = ai và cập nhật lại thông tin tổng T[ ] cho tất cả các nút chứa phần tử ai trong phạm vi quản lý. procedure Update(k,l,r: longint; i,v: longint); var x: longint; begin if (l>r) or (l>i) or(rr) (j < l ) or ( r < i) then Exit(0); if (i <= l ) and ( r <=j ) then Exit(T[k]); mid := (l+r) div 2; q1:= Query(2 * k, l, mid, i,j); q2:= Query(2 * k+1,mid+1, r, i,j); exit(q1+q2); end; Thủ tục truy vấn thông tin của đoạn sẽ được thực hiện bằng lời gọi Query(1,1,n,i,j). 3.1 Trường hợp biến đổi một dãy phần tử Trong trường hợp này chúng ta không cập nhật từ nút lá lên nút gốc mà cập nhật từ nút gốc xuống nút lá. Do đó khi cập nhật thông tin cho một nút k ta phải cập nhật thông tin lại cho tất cả các nút là hậu duệ của k mà việc làm này rất tốn thời gian và ảnh hưởng đến tốc độ của thuật toán. Để đảm bào thời gian thực hiện thuật toán là tối ưu đối với phép cập nhật khi có sự biến đổi trên một dãy phần tử thì người ta sử dụng phương pháp truyền lười (Lazy Propagation). Trong phương pháp truyền lười sử dụng cờ Lazy để ghi nhớ thông tin cần cập nhật của một nút. Lazy[k] ghi nhớ thông tin cần cập nhật của nút k. Ý tưởng của phương pháp truyền lười như sau: Phép toán cập nhật thông tin cho nút k, Update(k): - Cập nhật thông tin Lazy[k] cho nút k, không cập nhật thông tin Lazy[k] cho cac nút là hậu duệ của k nhưng phải ghi nhớ thông tin Lazy[k] qua 2 cờ Lazy[2*k] và Lazy[2*k+1] để cập nhật lại cho cac nút là hậu duệ của k ở phép toán Query. - Nếu nút k quản lý đoạn nằm trong đoạn cần cập nhật thì cũng chỉ cập nhật thông tin cho nút k, không cập nhật cho cac nút là hậu duệ của k nhưng phải ghi nhớ thông tin cập nhật qua 2 cờ Lazy[2*k] và Lazy[2*k+1] để cập nhật lại cho cac nút là hậu duệ của k ở phép toán Query. Chính vì không cập nhật cho cac nút là hậu duệ của k đã làm giảm đáng kể thời gian thực hiện của phép toán Update. Phép toán truy vấn thông tin của nút k, Query(k): - Cập nhật thông tin Lazy[k] cho nút k - Truy vấn thông tin nút k Ví dụ: 6 Cho một dãy gồm n số nguyên A=(a1, a2, ..., an). Xét hai phép biến đổi: - Phép cập nhật Update(i,j, v): Tăng các phần tử từ ai đến aj thêm giá trị v - Phép truy vấn Query(i,j): Trả về tổng các phần tử từ ai tới aj Yêu cầu: Cho dãy thao tác thực hiện tuần tự, hãy trả lời tất cả các truy vấn Query Input - Dòng 1 chứa 2 số nguyên dương n, k ≤ 105 - Dòng 2 chứa n số nguyên a1, a2, ..., an - n dòng tiếp, mỗi dòng cho thông tin về một phép biến đổi. Mỗi dòng bắt đầu bởi một ký tự {U,Q} + Nếu ký tự đầu dòng là “U” thì tiếp theo là hai số nguyên i, v tương ứng với phép cập nhật Update(i,v) (v ≤ 105) + Nếu ký tự đầu dòng là “Q” thì tiếp theo là hai số nguyên i, j tương ứng với phép truy vấn Query(i,j) (i < j) Output Trả lời tất cả các truy vấn , với mỗi truy vấn in ra câu trả lời trên 1 dòng Ví dụ: Input Output 95 32 1 2 3 4 5 6 7 8 75 9 U125 U356 Q14 U891 Q19 Sử dụng mảng T lưu trữ cây quản lý đoạn. T[k] là tổng giá trị của đoạn mà nút k quản lý. Sử dụng mảng Lazy ghi nhớ thông tin cần cập nhật. Lazy[k] là thông tin cần cập nhật của nút k. Xây dựng cây quản lý đoạn procedure Build(k: longint; l,r: longint); begin if ( l>r) then exit; {nếu k là nút lá} if ( l = r) then begin T[k] := a[l] 7 exit; End; {nếu k không là nút lá} Build(2*k, l, (l+r) div 2); Build(2*k + 1, (l+r) div 2 + 1, r); T[k] := (T[2 * k] + T[2 * k + 1]); end; Thủ tục khởi tạo cây quản lý đoạn sẽ được thực hiện bằng lời gọi Build(1,1,n). Cập nhật thông tin cho đoạn procedure update(k, l, r:longint; i, j, x:longint); var mid:longint; begin if (lazy[k]<>0) then begin t[k]:=t[k]+lazy[k]*(r-l +1); if (l<>r) then begin lazy[2*k]:= lazy[2*k]+lazy[k]; lazy[2*k +1]:= lazy[2*k +1]+lazy[k]; end; lazy[k]:=0; end; if ( l> r) or(l>j) or(rr) then begin lazy[2*k]:= lazy[2*k]+x; lazy[2*k +1]:= lazy[2*k +1]+x; end; exit; end; mid:=(l+r) div 2; update(2*k, l, mid, i, j, x); update(2*k+1, mid+1,r, i, j, x); t[k]:= t[2*k] + t[2*k+1]; 8 end; Thủ tục cập nhật thông tin cho đoạn sẽ được thực hiện bằng lời gọi Update(1,1,n,i,j,x). Truy vấn thông tin của đoạn function query(k,L,R:longint; i,j:longint):longint; var q1,q2,mid:longint; begin if (lazy[k]<>0) then begin t[k]:=t[k]+lazy[k] *(r-l +1); if (l<>r) then begin lazy[2*k]:= lazy[2*k]+lazy[k]; lazy[2*k +1]:= lazy[2*k +1]+lazy[k]; end; lazy[k]:=0; end; if (l>r)or(L>j) or (r=b then exit(a); exit(b); end; function min(a,b: longint): longint; begin if a<=b then exit(a); exit(b) end; procedure build(k,l,r: longint); 10 var m: longint; begin if(l>r) then exit; if l=r then begin Tmax[k]:=a[l]; Tmin[k]:=a[l]; exit; end; m:=(l+r) div 2; build(2*k,l,m); build(2*k+1,m+1,r); Tmax[k]:=max(Tmax[2*k],Tmax[2*k+1]); Tmin[k]:=min(Tmin[2*k],Tmin[2*k+1]); end; procedure Query(k,l,r:longint; i,j: longint; var maxx,minn: longint); var qma1,qma2,qmi1,qmi2, mid:longint; begin if(l>r) or (l>j) or(rb.g then exit(a) else exit(b); end; procedure Build(x,l,r: longint); var g: longint; begin if l>r then exit; if l=r then begin t[k].g:=a[l]; t[k].id:=l; exit; end; 13 g:=(l+r) div 2; Build(2*k,l,g); Build(2*k+1,g+1,r); t[k]:=max(t[2*k],t[2*k+1]); end; procedure update(k,l,r:longint; i,x: longint); var g: longint; begin if (l>r) or (ri) then exit; if (l=i) and (r=i) then begin t[k].g:=x; exit; end; g:=(l+r) div 2; update(2*k,l,g,i,x); update(2*x+1,g+1,r,i,x); t[k]:=max(t[2*k],t[2*k+1]); end; function Query(k,l,r:longint; i,j: longint): nut; var g: longint; q1,q2:nut; begin if (l>r) or (rj) then exit(vc); if (i<=l) and (r<=j) then exit(t[k]); g:=(l+r) div 2; q1:=Query(2*k,l,g,i,j); q2:=Query(2*k+1,g+1,r,i,j) exit(max(q1,q2)); end; procedure xuly; var kq,x,y,i: longint; c: char; nhi,nhat,q1,q2:nut; begin assign(f,fi); reset(f); assign(g,fo); rewrite(g); readln(f,n); 14 for i:=1 to n do read(f,a[i]); Build(1,1,n); vc.g:=-vcc; vc.id:=0; readln(f,m); for i:=1 to m do Begin readln(f,c,x,y); if c='U' then update(1,1,n,x,y) else begin nhat:=Query(1,1,n,x,y); q1:=Query(1,1,n,x,kq.id-1); q2:=Query(1,1,n,kq.id+1,y); nhi:=max(q1,q2); kq:=nhat.g + nhi.g; writeln(g,kq); end; end; close(f); close(g); end; BEGIN xuly END. Bài 3. Giá trị lớn nhất (QMAX) 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 15 - Dòng thứ m+2: q - q dòng tiếp theo, mỗi dòng chứa u, v cho biết một câu hỏi Output Gồm q dòng chứa kết quả tương ứng cho từng câu hỏi. Ví dụ: Input Output 62 3 132 463 1 34 Code chương trình tham khảo CONST FI=''; FO=''; MAXN=50000; VAR A:ARRAY[1..MAXN+1] of longint; T:array[1..4*maxn] of longint; Lazy:array[1..4*maxn] of longint; n,m,p:longint; f,g:text; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure update(k, l, r:longint; i, j, x:longint); var mid:longint; begin if (lazy[k]<>0) then begin t[k]:=t[k]+lazy[k]; if (l<>r) then begin lazy[2*k]:= lazy[2*k]+lazy[k]; lazy[2*k +1]:= lazy[2*k +1]+lazy[k]; end; lazy[k]:=0; 16 end; if ( l> r) or(l>j) or(rr) then begin lazy[2*k]:= lazy[2*k]+x; lazy[2*k +1]:= lazy[2*k +1]+x; end; exit; end; mid:=(l+r) div 2; update(2*k, l, mid, i, j, x); update(2*k+1, mid+1,r, i, j, x); t[k]:= max(t[2*k],t[2*k+1]); end; function query(k,L,R:long; i,j:longint):longint; var q1,q2,mid:longint; begin if (lazy[k]<>0) then begin t[k]:=t[k]+lazy[k]; if (l<>r) then begin lazy[2*k]:= lazy[2*k]+lazy[k]; lazy[2*k +1]:= lazy[2*k +1]+lazy[k]; end; lazy[k]:=0; end; if (l>r)or(L>j) or (rb then exit(a) else exit(b); end; procedure update(k, l, r:longint; i, j, x:longint); var mid:longint; begin if (lazy[k]<>0) then begin t[k]:=t[k]+lazy[k]; if (l<>r) then begin lazy[2*k]:= lazy[2*k]+lazy[k]; lazy[2*k +1]:= lazy[2*k +1]+lazy[k]; end; lazy[k]:=0; end; 19 if ( l> r) or(l>j) or(rr) then begin lazy[2*k]:= lazy[2*k]+x; lazy[2*k +1]:= lazy[2*k +1]+x; end; exit; end; mid:=(l+r) div 2; update(2*k, l, mid, i, j, x); update(2*k+1, mid+1,r, i, j, x); t[k]:= max(t[2*k],t[2*k+1]); end; function query(k,L,R:longint; i,j:longint):int64; var mid:longint; q1,q2:int64; begin if (lazy[k]<>0) then begin t[k]:=t[k]+lazy[k]; if (l<>r) then begin lazy[2*k]:= lazy[2*k]+lazy[k]; lazy[2*k +1]:= lazy[2*k +1]+lazy[k]; end; lazy[k]:=0; end; if (l>r)or(L>j) or (r