Tutorial — Mạng Dịch Chuyển

Thao tác di chuyển $k$ bước tương đương với việc lặp lại phép hợp hàm chuyển tiếp $k$ lần từ máy chủ ban đầu. Với $k$ lớn lên tới $10^9$, việc mô phỏng duyệt từng bước tuần tự sẽ bị quá thời gian cho phép.

Do phép hợp hàm có tính chất kết hợp, kết quả di chuyển $2^j$ bước có thể thu được bằng cách di chuyển hai lần liên tiếp $2^{j-1}$ bước. Nếu biết trước vị trí dừng sau các khoảng cách là lũy thừa của $2$, ta có thể ghép chúng lại để tạo thành $k$ bước bất kỳ.

Sử dụng kỹ thuật nhảy nhị phân (Binary Lifting) bằng cách tiền xử lý mảng $up[j][i]$ lưu máy chủ đạt được từ $i$ sau $2^j$ bước dựa trên công thức $up[j][i] = up[j-1][up[j-1][i]]$. Với mỗi truy vấn, phân tích $k$ thành tổng các dạng $2^j$ tương ứng với các bit bật để thực hiện nhảy trong thời gian $O(\log k)$.