Tutorial — Tính Lưu Lượng Mạng

Mạng máy tính tạo thành một đồ thị cây nên giữa hai máy chủ bất kỳ chỉ có duy nhất một đường đi đơn. Việc duyệt cây để tăng lưu lượng trên từng đường truyền cho mỗi yêu cầu truyền dữ liệu sẽ khiến thời gian chạy tăng lên mức $O(k \cdot n)$.

Tương tự kỹ thuật mảng chênh lệch trên mảng một chiều, ta có thể quản lý lưu lượng bằng cách lưu giá trị chênh lệch $d[u]$ tại mỗi máy chủ $u$, sao cho tổng giá trị $d[v]$ trong cây con gốc $u$ bằng lưu lượng qua đường truyền nối $u$ với cha của nó.

Với mỗi yêu cầu truyền dữ liệu giữa hai máy chủ $a$ và $b$, ta tìm $L = \text{LCA}(a, b)$ bằng bảng nhảy nhị phân, sau đó cập nhật $d[a] \leftarrow d[a] + 1$, $d[b] \leftarrow d[b] + 1$ và $d[L] \leftarrow d[L] - 2$. Cuối cùng, dùng thuật toán duyệt DFS để cộng dồn giá trị trên cây con nhằm thu được đáp án cho tất cả đường truyền trong thời gian $O((n + k) \log n)$.