15

VNOI Wiki Project - Lowest Common Ancestor (LCA) - Binary Lifting

posted on March 21, 2022, 8:03 a.m.

Chào các bạn,

Bài toán tìm tổ tiên chung gần nhất (Lowest Common Ancestor - LCA) là một dạng bài quen thuộc thường gặp trong các cuộc thi lập trình thi đấu. Bài toán tìm LCA có nhiều cách giải khác nhau, bên cạnh những cách quen thuộc với chúng ta như sử dụng Euler Tour + RMQ thì kỹ thuật Nâng nhị phân (Binary Lifting) cũng là một trong những cách giải hiệu quả. Tiếp nối chuỗi các bài được dịch & nâng cấp của các bạn TNV, team VNOI xin giới thiệu bài viết mới với chủ đề Lowest Common Ancestor (LCA) - Binary Lifting.

Link bài viết: https://vnoi.info/wiki/algo/data-structures/lca-binlift.md

Biên soạn: Lê Minh Hoàng - Trường Phổ thông Năng khiếu - ĐHQG-HCM

Reviewer:

  • Trần Quang Lộc - ITMO University
  • Hồ Ngọc Vĩnh Phát - Đại học Khoa học Tự nhiên - ĐHQG-HCM
  • Nguyễn Phú Bình - Trường THPT Chuyên Hùng Vương - Bình Dương
  • Trần Xuân Bách - Trường THPT Chuyên Khoa học Tự nhiên - ĐHQGHN

Cảm ơn các bạn TNV đã chuẩn bị bài viết này. Cũng thông qua bài viết, chúng mình hi vọng các bạn có thể hiểu rõ hơn về cách ứng dụng kỹ thuật Binary Lifting vào bài toán LCA. Chúc các bạn học tập hiệu quả!


Chuỗi các bài được dịch & nâng cấp của VNOI Wiki là chuỗi các chủ đề, blog hay được dịch và nâng cấp, hoàn thiện qua sự hỗ trợ của các bạn TNV VNOI. Qua đây, chúng mình mong rằng thư viện thuật toán VNOI Wiki sẽ trở thành nguồn tài liệu tham khảo bằng tiếng Việt tốt nhất cho các bạn có niềm đam mê với thuật toán và Lập trình thi đấu. Trong thời gian sắp tới, VNOI Wiki sẽ tiếp tục có nhiều chủ đề hay và thú vị hơn, các bạn cùng đón chờ nhé!


Comments

Please read the guidelines before commenting.


There are no comments at the moment.