Tác giả:
Reviewer:
Heavy-Light Decomposition (HLD), dịch ra tiếng Việt là phân chia nặng nhẹ là một kỹ thuật thường được dùng trong những bài toán xử lý trên cây.
Trong bài viết này, để ngắn gọn và dễ nhớ, chúng ta sẽ gọi tên kỹ thuật là HLD.
Tuy nghe tên có vẻ kinh khủng nhưng trên thực tế, đây là một kỹ thuật có ý tưởng khá tự nhiên và có tính ứng dụng cao, có thể được sử dụng trong nhiều bài tập.
Để trả lời câu hỏi HLD sẽ giúp chúng ta làm gì, chúng ta sẽ cùng giải một bài toán.
Trước hết, chúng ta sẽ đến với phiên bản dễ hơn của bài toán như sau.
Cho một mảng số nguyên dương gồm tối đa phần tử. Chúng ta cần xử lý tối đa truy vấn thuộc một trong hai loại sau:
Bài toán trên là một bài toán quen thuộc và có thể được xử lý đơn giản bằng cách sử dụng Segment Tree. Nhưng, giả sử thay vì mảng một chiều, chúng ta cần xử lý bài toán trên cây thì phải làm như thế nào?
Bạn đọc có thể đọc đề bài cụ thể và nộp code tại đây
Cho một cây (một đồ thị có đỉnh và cạnh và giữa hai đỉnh bất kỳ có đúng một đường đi giữa chúng). Mỗi đỉnh được gán một giá trị. Chúng ta cần xử lý hai loại truy vấn
Đường đi từ đến trên đồ thị được định nghĩa là một chuỗi các đỉnh trong đó tồn tại một cạnh nối giữa và , và , ..., đến , đến . Với mỗi cặp đỉnh , bất kỳ trên cây tồn tại một và chỉ một đường đi từ đến .
Vậy chính xác thì HLD sẽ làm gì để giúp chúng ta giải được phiên bản "trên cây" của bài toán trên? Liệu chúng ta có thể biến cây cho trước thành một mảng để giải bài toán trên đó? Câu trả lời là không. Tuy nhiên chúng ta có thể chia cây thành một số phần, và giải bài toán trên từng phần đó.
Cụ thể như sau, giả sử có cây sau đây
Không mất tính tổng quát, có thể coi đỉnh là gốc của cây. Với mỗi đỉnh không phải lá trên cây, chúng ta sẽ đánh dấu những cạnh nối đỉnh đó với con có kích thước cây con lớn nhất của của nó.
Ví dụ, xét đỉnh có ba đỉnh con lần lượt là đỉnh , và . Cây con ở hai đỉnh và có kích thước là , còn cây con ở đỉnh có kích thước là .
Vì vậy, chúng ta sẽ đánh dấu cạnh nối giữa đỉnh và đỉnh (tô màu đỏ). Làm tương tự với các đỉnh còn lại, chúng ta được cây như hình vẽ dưới đây.
Chúng ta sẽ gọi những cạnh màu đỏ là những "cạnh nặng" (heavy edges) vì chúng nối một đỉnh với đỉnh con "nặng nhất". Những cạnh còn lại sẽ được gọi là những "cạnh nhẹ" (light edges)
Có thể thấy rằng, những cạnh được đánh dấu sẽ tạo thành các "chuỗi" đi từ trên xuống dưới. Ví dụ như chuỗi hay chuỗi . Các đỉnh là lá cũng có thể coi là một chuỗi riêng.
Với cách quy ước trên, ta có thể thấy rằng hai chuỗi "liền nhau" được nối với nhau bởi một cạnh nhẹ. Hai chuỗi "liền nhau" là hai chuỗi mà tồn tại đỉnh nằm ở một chuỗi và nằm ở chuỗi còn lại sao cho và có cạnh nối trực tiếp với nhau. Do và khác chuỗi nên cạnh nối giữa và là cạnh nhẹ. Hai chuỗi không thể nối ở nhiều hơn một cặp điểm.
Khi đó, chúng ta có thể chứng minh được rằng đường đi giữa hai đỉnh bất kỳ trên cây đi qua không quá chuỗi. Bạn đọc có thể tự chứng minh nhận xét trên trước khi đọc chứng minh bên dưới.
Xét một đỉnh được nối với đỉnh cha của nó là bởi một cạnh nhẹ. Giả sử kích thước cây con của là và kích thước cây con của là . Do cạnh nặng đi từ không được nối xuống nên chắc chắn tồn tại một con khác của là có kích thước cây con . Vì vậy,
Do với mỗi lần nhảy qua cạnh nhẹ, kích thước của cây con ở đỉnh sau khi nhảy sẽ tăng ít nhất là gấp đôi nên ta có thể kết luận rằng để đi lên một tổ tiên bất kỳ ở phía trên thì có thể nhảy qua không quá cạnh nhẹ. Do mỗi lần đi qua cạnh nhẹ chính là một lần nhảy sang chuỗi mới nên từ một đỉnh lên tổ tiên bất kỳ của nó sẽ chỉ đi qua chuỗi.
Khi đó, từ hai đỉnh , bất kỳ, chúng ta có thể tìm LCA của , và đi từ , đến LCA. Số chuỗi đi qua sẽ không quá
Ngoài ra, nếu ta duyệt cây bằng DFS ưu tiên các đỉnh liền trong chuỗi trước, ta có thể nhận thấy là các đỉnh trên cùng một chuỗi sẽ nằm kế tiếp nhau trên thứ tự DFS, và vì thế việc truy vấn một đoạn con bất kì trên một chuỗi nào đó có thể được thực hiện trên Segment tree với độ phức tạp là .
Như vậy, chúng ta đi qua không quá chuỗi, với mỗi chuỗi chúng ta có thể thực hiện trả lời truy vấn hoặc update trong trên Segment tree nên độ phức tạp cho việc trả lời các truy vấn và cập nhật trên một đường đi giữa hai đỉnh bất kỳ trên cây là
Thông thường, do việc sử dụng HLD sẽ đi kèm với một cấu trúc dữ liệu nào đó và duyệt đồ thị, code có thể sẽ dài và gồm nhiều phần. Tuy nhiên, nếu nắm chắc ý tưởng chính thì cài đặt HLD rất đơn giản.
Đầu tiên, ta cần phải tính kích thước của cây con từng đỉnh để lấy ra các con "nặng" của từng đỉnh một. Ngoài ra, ta cần tính thêm độ sâu các đỉnh để phục vụ cho thao tác tính LCA.
void Dfs(int s, int p = -1) {
Sz[s] = 1;
for(int u: AdjList[s]) {
if(u == p) continue;
Par[u] = s;
Depth[u] = Depth[s] + 1;
Dfs(u, s);
Sz[s] += Sz[u];
}
}
mảng và lần luợt lưu kích thuớc cây con, độ sâu và cha (tổ tiên trực tiếp) của các đỉnh trên cây
mảng là mảng vector để lưu lại thông tin về đồ thị. là vector gồm các đỉnh kề với .
Sau đó chúng ta thực hiện phân chia các đỉnh vào các chuỗi. Với mỗi đỉnh, cần lưu lại chuỗi của đỉnh và vị trí của đỉnh khi đặt các chuỗi liên tiếp với nhau (để thuận tiện cho việc xử lý truy vấn). Với mỗi chuỗi, chúng ta cần biết đỉnh đầu tiên của chuỗi (để thực hiện việc nhảy giữa các chuỗi).
void Hld(int s, int p = -1) {
if(!ChainHead[CurChain]) {
ChainHead[CurChain] = s;
}
ChainID[s] = CurChain;
Pos[s] = CurPos;
Arr[CurPos] = s;
CurPos++;
int nxt = 0;
for(int u: AdjList[s]) {
if(u != p) {
if(nxt == 0 || Sz[u] > Sz[nxt]) nxt = u;
}
}
if(nxt) Hld(nxt, s);
for(int u: AdjList[s]) {
if(u != p && u != nxt) {
CurChain++;
Hld(u, s);
}
}
}
là biến dùng để lưu lại đỉnh con "nặng nhất".
là mảng dùng để lưu lại các chuỗi.
là mảng lưu lại số thứ tự của các chuỗi.
là mảng lưu lại node đầu tiên ( bé nhất) của từng chuỗi để biết khi nào cần nhảy sang chuỗi mới qua cạnh nhẹ.
Mảng lưu lại vị trí của các đỉnh trên để tiện xử lý trên segment tree.
và lần lượt là các biến lưu lại chỉ số của chuỗi và vị trí trong mảng để dùng cho chuỗi và đỉnh tiếp theo
Như vậy, với mỗi đỉnh, chúng ta sẽ tìm cạnh nặng và đi xuống cạnh đó trước. Sau đó, chúng ta sẽ lần lượt tạo ra các chuỗi mới và nhảy sang các đỉnh nhẹ. Như vậy, thứ tự duyệt đồ thị sẽ đảm bảo mỗi chuỗi được lưu đúng thứ tự từ trên xuống dưới trong một đoạn liên tiếp trên mảng .
Trong phần lớn các bài toán sử dụng HLD để thực hiện truy vấn trên đường đi, chúng ta cần tìm tổ tiên chung gần nhất và thực hiện thao tác lần lượt từ hai đỉnh đến tổ tiên chung này. Rất may là chúng ta có thể sử dụng chính những thông tin đã lưu để tìm ra LCA một cách nhanh chóng.
Khi nhảy từ một node qua một cạnh nhẹ lên cha của nó, chúng ta luôn nhảy sang một chuỗi có số thứ tự bé hơn (do thứ tự duyệt đồ thị trong hàm ) nên để tìm LCA của hai đỉnh, chúng ta sẽ tìm chuỗi chứa LCA đó.
Liên tục thực hiện nhảy từ chuỗi có số thứ tự lớn hơn lên một chuỗi có số thứ tự bé hơn (Để đảm bảo không bị nhảy quá, luôn chọn đỉnh đang ở chuỗi có số thứ tự lớn hơn để nhảy) cho đến khi hai đỉnh nằm trên cùng một chuỗi.
Ở đó, đỉnh có độ sâu thấp hơn là LCA của và .
int LCA(int u, int v) {
while(ChainID[u] != ChainID[v]) {
if(ChainID[u] > ChainID[v]) {
u = Par[ChainHead[ChainID[u]]];
}
else {
v = Par[ChainHead[ChainID[v]]];
}
}
if(Depth[u] < Depth[v]) return u;
return v;
}
Duới đây là các thao tác xử lý trên segment tree. Phần này sẽ đủ để xử lý phiên bản không trên cây của bài toán.
int ST[MaxN * 4];
void Build(int id, int l, int r) {
if(l == r) {
ST[id] = Val[Arr[l]];
return;
}
int mid = (l + r) / 2;
Build(id * 2, l, mid);
Build(id * 2 + 1, mid + 1, r);
ST[id] = ST[id * 2] ^ ST[id * 2 + 1];
}
void Upd(int id, int l, int r, int pos, int val) {
if (l > pos || r < pos) return;
if (l == r && l == pos) {
ST[id] = val;
return;
}
int mid = (l + r) / 2;
Upd(id * 2, l, mid, pos, val);
Upd(id * 2 + 1, mid + 1, r, pos, val);
ST[id] = ST[id * 2] ^ ST[id * 2 + 1];
}
int Calc(int id, int tl, int tr, int l, int r) {
if (tl > r || tr < l) return 0;
if (l <= tl && tr <= r) return ST[id];
int mid = (tl + tr) / 2;
return Calc(id * 2, tl, mid, l, r) ^ Calc(id * 2 + 1, mid + 1, tr, l, r);
}
Và cuối cùng, chúng ta sẽ có các hàm để xử lý truy vấn trên cây. Tất nhiên có thể đưa toàn bộ phần này vào trong main mà không tăng độ dài code. Tuy nhiên để dễ nhìn và tiện debug, chúng ta sẽ code riêng hàm để xử lý truy vấn trên đuờng đi từ đỉnh đến đỉnh .
void Update(int x, int val) {
Upd(1, 1, N, Pos[x], val);
}
int Query(int u, int v) {
int lca = LCA(u, v);
int ans = 0;
while(ChainID[u] != ChainID[lca]) {
ans ^= Calc(1, 1, N, Pos[ChainHead[ChainID[u]]], Pos[u]);
u = Par[ChainHead[ChainID[u]]];
}
while(ChainID[v] != ChainID[lca]) {
ans ^= Calc(1, 1, N, Pos[ChainHead[ChainID[v]]], Pos[v]);
v = Par[ChainHead[ChainID[v]]];
}
if(Depth[u] < Depth[v]) {
ans ^= Calc(1, 1, N, Pos[u], Pos[v]);
}
else {
ans ^= Calc(1, 1, N, Pos[v], Pos[u]);
}
return ans;
}
Do bài toán chỉ yêu cầu cập nhật trên điểm nên hàm không có gì đáng chú ý. Độ phức tạp của hàm này là .
Hàm dùng để trả lời truy vấn tổng XOR của các số trên đường đi từ đến . Sau đó, chúng ta thực hiện chia đường đi này thành các đoạn trên các chain rồi thực hiện thao tác tính trên từng đoạn.
Có thể thấy, cách nhảy trong khi tính toán Query chính là cách nhảy khi tìm LCA. Trên thực tế, chúng ta không cần tìm LCA trước mà có thể thực hiện việc đó ngay khi tính Query. Nhưng trong bài này, phần tìm LCA được code riêng một hàm để dễ hiểu và tiện giải thích.
Dưới đây là code đầy đủ cho bài toán (kết hợp của tất cả các đoạn trên, khai báo biến và hàm main) để bạn đọc tham khảo. (Code nộp AC)
#include<bits/stdc++.h>
using namespace std;
const int MaxN = 1e5 + 5;
int N, Q;
int Val[MaxN];
vector<int> AdjList[MaxN]; // input
int Par[MaxN]; // parent
int Depth[MaxN]; // do sau cua node
int Sz[MaxN]; // kich thuoc cua cay con cho cac node
int Pos[MaxN]; // vi tri trong mang cua node
int Arr[MaxN]; // gia tri cua cac phan tu trong mang
int ChainID[MaxN]; // ChainID[i]: Chain ma i nam trong
int ChainHead[MaxN]; // ChainHead[i]: Node dau tien trong chain i
int CurChain, CurPos;
void Dfs(int s, int p = -1) {
Sz[s] = 1;
for(int u: AdjList[s]) {
if(u == p) continue;
Par[u] = s;
Depth[u] = Depth[s] + 1;
Dfs(u, s);
Sz[s] += Sz[u];
}
}
void Hld(int s, int p = -1) {
if(!ChainHead[CurChain]) {
ChainHead[CurChain] = s;
}
ChainID[s] = CurChain;
Pos[s] = CurPos;
Arr[CurPos] = s;
CurPos++;
int nxt = 0;
for(int u: AdjList[s]) {
if(u != p) {
if(nxt == 0 || Sz[u] > Sz[nxt]) nxt = u;
}
}
if(nxt) Hld(nxt, s);
for(int u: AdjList[s]) {
if(u != p && u != nxt) {
CurChain++;
Hld(u, s);
}
}
}
// find LCA
int LCA(int u, int v) {
while(ChainID[u] != ChainID[v]) {
if(ChainID[u] > ChainID[v]) {
u = Par[ChainHead[ChainID[u]]];
}
else {
v = Par[ChainHead[ChainID[v]]];
}
}
if(Depth[u] < Depth[v]) return u;
return v;
}
// Segment Tree
int ST[MaxN * 4];
void Build(int id, int l, int r) {
if(l == r) {
ST[id] = Val[Arr[l]];
return;
}
int mid = (l + r) / 2;
Build(id * 2, l, mid);
Build(id * 2 + 1, mid + 1, r);
ST[id] = ST[id * 2] ^ ST[id * 2 + 1];
}
void Upd(int id, int l, int r, int pos, int val) {
if (l > pos || r < pos) return;
if (l == r && l == pos) {
ST[id] = val;
return;
}
int mid = (l + r) / 2;
Upd(id * 2, l, mid, pos, val);
Upd(id * 2 + 1, mid + 1, r, pos, val);
ST[id] = ST[id * 2] ^ ST[id * 2 + 1];
}
int Calc(int id, int tl, int tr, int l, int r) {
if (tl > r || tr < l) return 0;
if (l <= tl && tr <= r) return ST[id];
int mid = (tl + tr) / 2;
return Calc(id * 2, tl, mid, l, r) ^ Calc(id * 2 + 1, mid + 1, tr, l, r);
}
// Update and queries
void Update(int x, int val) {
Upd(1, 1, N, Pos[x], val);
}
int Query(int u, int v) {
int lca = LCA(u, v);
int ans = 0;
while(ChainID[u] != ChainID[lca]) {
ans ^= Calc(1, 1, N, Pos[ChainHead[ChainID[u]]], Pos[u]);
u = Par[ChainHead[ChainID[u]]];
}
while(ChainID[v] != ChainID[lca]) {
ans ^= Calc(1, 1, N, Pos[ChainHead[ChainID[v]]], Pos[v]);
v = Par[ChainHead[ChainID[v]]];
}
if(Depth[u] < Depth[v]) {
ans ^= Calc(1, 1, N, Pos[u], Pos[v]);
}
else {
ans ^= Calc(1, 1, N, Pos[v], Pos[u]);
}
return ans;
}
// main
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("cowland.in", "r", stdin);
freopen("cowland.out", "w", stdout);
cin >> N >> Q;
for(int i = 1; i <= N; i++) {
cin >> Val[i];
}
for(int i = 1; i < N; i++) {
int u, v;
cin >> u >> v;
AdjList[u].push_back(v);
AdjList[v].push_back(u);
}
CurPos = CurChain = 1;
Dfs(1);
Hld(1);
Build(1, 1, N);
while(Q--) {
int type;
cin >> type;
if(type == 1) {
// Update
int x, val;
cin >> x >> val;
Update(x, val);
}
else {
int u, v;
cin >> u >> v;
cout << Query(u, v) << '\n';
}
}
}
Bài viết trên được tham khảo từ bài viết gốc Hybrid Tutorial 1: Heavy-Light Decomposition. Bạn đọc có thể tham khảo và xem video hướng dẫn kèm theo của galen_colin. Ngoài ra có thể tham khảo bài viết của CP algo.
Trước hết, bạn đọc nên tự cài đặt và nộp bài tập phía trên tại đây. Sau đó có thể làm thêm các bài tập luyện tập dưới đây