Tài liệu Kĩ thuật heavy-light decomposition

Heavy-Light Decomposition Giới thiệu Kĩ thuật Heavy-Light Decomposition (còn gọi là heavy path decomposition, từ đây xin viếết tắết là HLD) được đưa ra lâần đâầu nắm 1983 b ởi Sleator và Tarjan trong bài báo "A data structure for dynamic trees", Journal of Computer and System Sciences 26 (3): 362–391 trong phâần phân tích ti ệm cận vếầ tính hiệu quả của câếu trúc link/cut tree c ủa họ. Nắm 1984, Harel và Tarjan lại sử dụng một lâần nữa kĩ thuật này trong bài báo "Fast algorithms for finding nearest common ancestors", SIAM Journal on Computing 13 (2): 338–355 vếầ tìm tổ tiến chung gâần nhâết c ủa hai nút trong một cây. HLD sớm chứng tỏ sức mạnh của nó trong nghiến c ứu đ ộ phức tạp của các thuật toán, các câếu trúc dữ liệu trến cây. Tưởng chừng HLD chỉ có ý nghĩa chủ yếếu trến phương diện lý thuyếết đ ộ phức tạp và chỉ là công cụ chứng minh toán học thuâần túy cho các bài báo thì đếến những nắm 2013-2014, trong các bài toán của nhiếầu cu ộc thi l ập trình online, HLD đã bước ra thực tiếễn và nhanh chóng th ể hi ện đ ược tính ưu việt của mình trong việc mô tả và xử lí các môếi quan hệ động giữa các đôếi tượng trong nhiếầu bài toán, đặc biệt trến câếu trúc cây v ới các truy vâến online. Chúng tôi xin cung câếp một cái nhìn sơ lược vếầ HLD và vài mở rộng của nó thông qua một sôế bài toán lập trình thuật toán, ngõ hâầu cùng quý v ị nắếm bắết kịp với xu hướng thay đổi chóng mặt vếầ gi ải thu ật cũng nh ư câếu trúc dữ liệu của các cuộc thi lập trình online, các cuộc thi l ập trình khu v ực và quôếc tếế. HLD trên cây Cây cân bằằng Ta đã biếết cây cân bắầng là một câếu trúc tôết trong l ập trình. M ột cây cân bắầng nút có độ cao , điếầu này cho ta hai tính châết:  Ta câần duyệt qua không quá nút để đếến được nút gôếc từ một nút bâết kì trong cây;  Ta câần duyệt qua không quá nút để di chuyển từ một nút bâết kì đếến một nút bâết kì khác trong cây. Hệ sôế luôn tôết cho mọi bài toán. Với một cây cân bắầng quyếết được một loạt các truy vâến bắầng độ phức tạp nút, ta giải . Chẳng hạn: khoảng cách giữa hai nút, trọng sôế lớn/nhỏ nhâết trến một đ ường đi, t ổng liến tiếếp lớn nhâết của các đoạn liến tiếếp, … Chuỗỗi tuyếến tính Một dãy các nút được nôếi tiếếp tuyếến tính cũng là m ột câếu trúc tôết. Ta có thể xây dựng các segment tree hay binary indexed tree (là các cây cân bắầng) cho chuôễi để giải quyếết bắầng độ phức tạp các truy vâến dạng max, min, tổng đoạn, … trến chuôễi. Cây khỗng cân bằằng Độ cao của một cây không cân bắầng dao động trong một ph ạm vi quá l ớn ( ). Với trường hợp suy biếến, ta phải duyệt qua nút để từ một nút này di chuyển đếến một nút khác. Ta xem xét dưới đây cách đôếi phó với một cây không cân bắầng tương đôếi đặc biệt. Bài toán: cho cây như hình veễ, tính tổng trọng sôế các nút trến đường đi (đơn) giữa hai nút bâết kì, giả thiếết trọng sôế các nút có th ể thay đ ổi theo thời gian/truy vâến. Có thể nhận thâếy:  Cây có nút  Ta câần thắm nút để di chuyển từ đếến  Ta thắm ít nhâết nút để di chuyển từ đếến  Ta thắm ít nhâết nút để di chuyển từ đếến Như vậy rõ ràng câần chi phí để di chuyển giữa hai nút tùy ý trong cây. Để đôếi phó, ta thử bẻ cây thành ba chuôễi như hình veễ: Với môễi chuôễi ta có thể xây dựng segment tree cho riếng nó và truy vâến trến môễi chuôễi seễ xuâết hiện yếếu tôế log. Ta nhận thâếy:   Cây vâễn có nút, nhưng đã được phân rã thành ba chuôễi độ dài thuộc cùng một chuôễi, truy vâến giữa chúng được giải quyếết trong  thuộc hai chuôễi khác nhau, đường đi giữa chúng có th ể tách thành , truy vâến giữa , chính xác là mâết hai lâần được giải quyếết trong  Tương tự: thuộc hai chuôễi khác nhau, đường đi giữa chúng có thể tách thành , truy vâến giữa chúng được giải quyếết trong , chính xác là là mâết ba lâần Như vậy, với cây đã cho, bắầng phép phân rã thành ba chuôễi và xây d ựng segment tree kèm theo môễi chuôễi, truy vâến giữa hai nút bâết kì tôến chi phí . Vâến đếầ là: cây trến chỉ có đúng hai nút có b ậc ba nến ta có đ ược m ột phân rã tỗết, đường đi giữa hai nút bâết kì tách thành không quá ba đo ạn chuôễi. Điếầu gì xảy ra nếếu cây là cây tổng quát? Ta câần một kĩ thu ật phân rã ph ức tạp hơn nhắầm đạt được độ phức tạp châếp nhận được ngay cả trong trường hợp xâếu nhâết. Đó chính là HLD. Phân rã Heavy-Light Ta seễ phân rã cây thành các chuôễi rời (không có hai chuôễi nào có nút chung) theo cách sao cho đường đi từ nút gôếc đếến một nút bâết kì trong cây phải chuyển qua không quá chuôễi. Nghĩa là phân rã phải thỏa mãn: đường đi từ nút gôếc đếến một nút bâết kì có th ể tách thành các m ảnh, môễi mảnh thuộc một chuôễi và có không quá mảnh. Nếếu thực hiện được phân rã như trến, với hai nút bâết kì đường đi từ đếến thành hai phâần: đếến ; đếến , ta xét tách , và dạng truy vâến chung của chúng là: từ một nút, đi lến một nút tổ tiến của nó. Với giả thiếết phân rã đã có ta thâếy ngay độ ph ức tạp c ủa m ột truy vâến seễ là Việc còn lại là chỉ ra cách phân rã đó. Xét một cây tổng quát, ta đặt ra các khái niệm:   Nút con nặng (heavy): trong sôế các nút con của một nút, nút con ứng với cây con nặng nhâết (nhiếầu nút nhâết) đ ược gọi là nút con n ặng, các nút con còn lại được gọi là nút con nh ẹ (light). Môễi nút trong ch ỉ có đúng một nút con nặng. Cạnh nặng: với môễi nút trong, cạnh nôếi nút đó với con nặng c ủa nó được gọi là một cạnh nặng, các cạnh còn lại được gọi là cạnh nhẹ. Bắầng việc tô màu tâết cả các cạnh nặng, ta thu được phân rã HLD, môễi chuôễi là một dãy cạnh được tô màu liến thuộc nôếi tiếếp. Do môễi nút trong chỉ có đúng một nút con nặng nến các chuôễi là đôi m ột r ời nhau. H ơn thếế, môễi chuôễi đếầu là một đường nôếi một nút đếến một tổ tiến c ủa nút đó. Các cạnh nhẹ đóng vai trò kếết nôếi các chuôễi. Ta xem xét việc di chuyển từ một nút con nhẹ , do theo một cạnh nhẹ xuôếng một nút là nút con nhẹ nến cây con gôếc có kích thước không vượt quá một nửa cây con gôếc . Lại xem xét việc di chuyển từ nút gôếc của cây xuôếng một nút lá, do môễi lâần đi vào một cạnh nhẹ thì kích thước cây con giảm một nửa nến sôế cạnh nhẹ phải qua nhiếầu nhâết là Vì cạnh nhẹ đóng vai trò kếết nôếi các chuôễi nến điếầu đó cũng có nghĩa là phân rã ta v ừa xây d ựng hoàn toàn thỏa mãn các yếu câầu đếầ ra. Các vâến đếằ vếằ cài đặt Để khởi tạo HLD và giải quyếết bài toán ta câần hi ện th ực hóa các công việc:  Tính kích thước cho một cây con gôếc bâết kì. Xác định các cạnh nặng, nút con nặng, qua đó kếết nôếi thành các chuôễi.  Xây dựng segment tree cho môễi chuôễi.  Xây dựng sparse table phục vụ bài toán tìm tổ tiến chung gâần nhâết.  Các thông tin hôễ trợ câần thiếết:     Với môễi nút, câần biếết nó thuộc chuôễi nào. Với môễi nút, câần biếết vị trí của nó trong chuôễi. Với môễi chuôễi, câần biếết nút đâầu tiến của chuôễi (nút tổ tiến). Với môễi chuôễi, câần biếết độ dài của chuôễi. Với môễi truy vâến cập nhật trọng sôế, câần thực hiện:   Thay đổi trực tiếếp trến cạnh nhẹ. Thay đổi trong segment tree tương ứng với cạnh nặng. Với môễi truy vâến hỏi thông tin giữa hai nút  Xác định  Lâếy thông tin trến đường o , câần thực hiện: . Lặp cho đếến khi , ta xét tổng quát cùng chuôễi : lâếy thông tin từ : đếến đâầu chuôễi chứa , lâếy thông tin cạnh nhẹ nôếi đâầu chuôễi chứa với nút cha trực tiếếp, thay bởi nút cha trực tiếếp. o Khi cùng chuôễi, lâếy thông tin vếầ đoạn trong chuôễi đó. o Tổng hợp thông tin. Toàn bộ các công việc kể trến đếầu có độ phức tạp ). Một ứng dụng tư tưởng của HLD Blocking Xét bài toán cơ bản: cho dãy phâần tử, thực hiện các truy vâến: cập nhật giá trị một phâần tử nào đó, hỏi thông tin không cộng tính (max, min, …) của một đoạn phâần tử liến tiếếp nào đó. Nhớ lại những gì ta thường làm khi Segment tree, Binary Indexed tree và các câếu trúc tương tự chưa xuâết hiện (chưa biếết). Cách 1. Brute force  Thay đổi trực tiếếp phâần tử với truy vâến cập nhật. Độ phức tạp  Duyệt qua tâết cả các phâần tử của đoạn đôếi với truy vâến h ỏi. Đ ộ phức tạp . Cách 2. Blocking (bằm khỗếi) Chia dãy thành đoạn rời, gọi là các khôếi, môễi khôếi là một đoạn độ dài . Duy trì dãy thông tin của từng khôếi. Các truy vâến được xử lí như sau:  Truy vâến cập nhật: cập nhật phâần tử, duyệt và cập nhật thông tin khôếi chứa phâần tử đó. Độ phức tạp  Truy vâến hỏi thông tin đoạn . : xác định khôếi chứa phâần tử thứ , xác định khôếi chứa phâần tử thứ ; xác định thông tin các khôếi xen giữa hai khôếi vừa tìm được; xác định thông tin nửa khôếi ph ải ch ứa ; xác định thông tin nửa khôếi trái chứa ; kếết hợp các thông tin. Độ phức tạp . Có thể nhận thâếy HLD cũng cùng một tư tưởng xuâết phát v ới kĩ thu ật blocking. Đó là phân rã không gian tìm kiếếm thành các m ảnh, khôếi và duy trì các câếu trúc lưu giữ thông tin, hôễ trợ truy vâến thông tin trến các m ảnh, khôếi. Điểm đặc biệt của HLD là ta giữ môếi liến hệ giữa các khôếi tôết hơn. Sau đây ta tìm cách kếết hợp hai kĩ thuật này trong m ột bài toán vếầ t ập hợp. HLD cho tập hợp Bài toán: cho dãy sôế t ập kí hiệu là và với tập chỉ sôế . Phâần tử của . Tổng kích thước các tập cỡ . Giải quyếết hai loại truy vâến trến dãy :  “? K”: tính tổng tâết cả các phâần tử của có chỉ sôế nắầm trong tập : gia tắng một lượng  cho tâết cả các phâần tử của có chỉ sôế nắầm trong tập Hướng giải quyếết có thể tóm tắết như sau:  Coi một tập là nặng nếếu , được đưa vào nặng được quản lí thông qua vị trí nó được đưa vào này , các tập (vì sôế ). Các tập còn lại gọi là nhẹ.  Các phâần tử của tập nặng được duy trì danh sách nh ững t ập n ặng nó có tham gia.  Môễi tập (cả nặng và nhẹ) đếầu xác định sôế phâần t ử mà nó có chung với từng tập nặng (nhờ danh sách trến)  Giá trị phâần tử được lưu là các giá trị riếng, bỏ qua các lâần đ ược tắng ở tập nặng.  Duy trì mảng tổng của các tập bỏ qua việc tắng đếầu của các t ập nặng, mảng ghi nhớ lượng tắng đếầu vào các tập nặng, chúng đ ược gọi tắết là tổng riếng và lượng tắng.  Xét truy vâến o Nếếu là tập nặng, gia tắng lượng tắng của , chi phí o Nếếu là tập nhẹ, thay đổi trực tiếếp phâần tử trong t ập, chi phí o Tổng riếng của các tập nặng được tắng theo sôế phâần t ử chung với tập , chi phí  . Xét truy vâến o Nếếu là tập nặng, kếết quả là: tổng riếng lượng tắng kích thước, chi phí o Nếếu là tập nhẹ, kếết quả là: tổng các giá trị riếng chung với từng tập nặng lượng tắng của tập đó. Chi phí của cả hai pha duyệt phâần tử của tập là sôế lâần , duyệt các tập nặng đếầu . Trong cách giải quyếết trến, bắầng việc tách rời hoàn toàn các lâần tắng trến môễi tập nặng, ta đã khéo léo thiếết lập môếi quan h ệ gi ữa các t ập nói chung với từng tập nặng. Qua đó châếp nhận việc duyệt tắng giá trị riếng c ủa phâần tử trến các tập nhẹ với chi phí châếp nhận được. Việc kếết hợp tiếu chuẩn phân loại Heavy-Light c ủa HLD v ới c ận đ ộ ph ức t ạp của blocking đã cho một giải thuật đẹp cho một bài toán khó. Kết luận Các giải thuật, câếu trúc dữ liệu, kĩ thuật lập trình mới liến t ục n ảy sinh theo thời gian. Bắết kịp với xu hướng đó của cộng đôầng l ập trình thu ật toán trến thếế giới là nhu câầu cắn bản của môễi chúng ta. Qua HLD và m ột ứng dụng kếết hợp HLD với blocking được trình bày ở trến, có th ể thâếy rắầng: cái mới nhiếầu khi chẳng qua chỉ là tìm tòi, phát tri ển, kếết h ợp t ừ nhiếầu thứ đã râết cũ kĩ, quen thuộc. Hy vọng rắầng cộng đôầng chúng ta có thể đào sâu nghiến cứu và sáng tạo thếm nhiếầu kếết quả m ới, đ ẹp h ơn, hiệu quả hơn, đóng góp vào dòng chảy tiếến lến của thếế gi ới l ập trình thuật toán.