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.
- Xem thêm -