ปัญหาระดับบรรพบุรุษ

ขั้นตอนวิธีตัวชี้กระโดด

ขั้นตอนวิธีตัวชี้กระโดด (Jump pointer algorithm) เป็นขั้นตอนวิธีแบบกำหนดการพลวัต อาศัยการคำนวณล่วงหน้าโดยการสร้างแถวลำดับ 2 มิติ ชื่อ dp ขนาด n × log n โดย dp[v][p] จะชี้ไปยังจุดยอดที่อยู่สูงขึ้นไปจากจุดยอด v เป็นจำนวน 2ᵖ ขั้น อาศัยความสัมพันธ์ว่า dp[v][p] = dp[dp[v][p - 1]][p - 1] และกรณีฐานว่า dp[v][0] คือพ่อของจุดยอด v ก็จะสามารถเติมตาราง dp ได้ในเวลา O(n log n)
ในการหาคำตอบ ให้เริ่มต้นจากจุดยอด v และกระโดดโดยใช้ตัวชี้จาก dp ไปให้สูงที่สุดแต่ไม่ไปไกลเกินจุดยอดเป้าหมาย และกระโดดต่อจากจุดยอดนั้นไปเรื่อย ๆ จนกว่าจะเจอจุดยอดเป้าหมาย เนื่องจากการหาตัวชี้ที่จะใช้นั้นสามารถทำได้ใน O(1) จากสูตร \lfloor\log_2( (\operatorname{depth}(v) - d)\rfloor และการกระโดดแต่ละครั้งจะเหลือระยะห่างน้อยลงไป 2 เท่า จึงทำให้ใช้เวลา O(log n) ในการกระโดด

ขั้นตอนวิธีบันได

ขั้นตอนวิธีบันได (Ladder algorithm) ใช้แนวคิดที่ว่าปัญหาระดับบรรพบุรุษสามารถแก้ได้อย่างง่ายดายหากกราฟต้นไม้ที่จะประมวลผลเป็นกราฟวิถี เนื่องจากสามารถเปลี่ยนวิถีดังกล่าวไปเป็นแถวลำดับได้ และในการตอบคำถามก็เป็นเพียงการเรียกข้อมูลจากแถวลำดับโดยตรง อย่างไรก็ตามแนวคิดนี้ใช้ไม่ได้กับกราฟต้นไม้ทั่วไปที่มีกิ่งแตกออกมามากมาย จึงใช้วิธีแบ่งต้นไม้ออกเป็นหลาย ๆ วิถี และเก็บข้อมูลของวิถีต่าง ๆ ไว้ในแถวลำดับ และดำเนินการด้วยแนวคิดดังที่กล่าวมา สังเกตว่าด้วยวิธีนี้แล้วการกระโดดเพื่อหาคำตอบปัญหาระดับบรรพบุรุษแต่ละครั้งสามารถกระโดดข้ามไปเป็นวิถีได้เลย

การแยกส่วนของวิถียาวสุด

การแยกส่วนของวิถียาวสุด (Longest path decomposition) เป็นการหาวิถียาวสุดจากรากของต้นไม้ไปถึงใบทั้งหลาย หลังจากหาได้แล้วก็จะนำจุดยอดในวิถียาวสุดไปเรียงเก็บไว้ในแถวลำดับ 'LP' จากรูป 1. ก็จะได้ว่าวิถียาวสุดคือวิถีจาก r → v ดังนั้น LP ของ r ก็จะมีข้อมูล LP[r][0] = r, LP[r][1] = a, ..., LP[r][5] = v หลังจากเก็บข้อมูลวิถีเสร็จแล้วก็จะทำการลบวิถีนี้ออกจากต้นไม้ ทำให้ต้นไม้ถูกแยกออกเป็นหลายส่วน ก็ให้เริ่มต้นขั้นตอนดังกล่าวอีกรอบโดยพิจารณาต้นไม้ย่อยทั้งหลายที่เหลือเป็นต้นไม้ใหม่ เมื่อดำเนินการไปเรื่อย ๆ ก็จะไม่เหลือจุดยอดในต้นไม้อีก และแต่ละจุดยอดก็จะเก็บอยู่ในแถวลำดับเพียงแค่ครั้งเดียวเท่านั้น
ในการดำเนินการดังกล่าว สามารถกระทำได้โดยทำการค้นหาในแนวลึก ซึ่งใช้เวลาในการดำเนินการ O(n) ส่วนในการหาคำตอบปัญหาระดับบรรพบุรุษ LA(v, d) ก็ให้เริ่มจากจุดยอด v และหาว่า v อยู่ใน LP ชุดไหน จากนั้นก็กระโดดไปยังต้นของ LP และกระโดดขึ้นหนึ่งขั้น และดำเนินการแบบนี้ซ้ำไปเรื่อย ๆ จนกว่าจะกระโดดไปเจอต้นของ LP ที่มีความลึกน้อยกว่า d ซึ่งแสดงให้เห็นว่า LP ชุดนั้นมีจุดยอดคำตอบอยู่ ก็สามารถคำนวณหาตำแหน่งของจุดยอดนั้นและตอบได้ภายในเวลา O(1) เลย
อย่างไรก็ตาม ในกรณีเลวร้ายมากสุด (รูป 2.) จะต้องใช้เวลาในการกระโดดระหว่างวิถีต่าง ๆ มากถึง Θ(√n) ซึ่งค่านี้สามารถลดได้จากการใช้การแยกส่วนของบันไดซึ่งเป็นหัวข้อถัดไป

การแยกส่วนของบันได

การแยกส่วนของบันได (Ladder decomposition) ใช้แถวลำดับ 'Ladder' มีลักษณะขั้นตอนวิธีแทบจะเหมือนกับการแยกส่วนของวิถียาวสุดทุกประการ แต่แตกต่างตรงที่แถวลำดับ Ladder นอกจากจะเก็บข้อมูลของลูกหลานของรากต้นไม้ย่อยแล้ว ยังเก็บข้อมูลบรรพบุรุษเป็นจำนวนข้อมูลเท่ากับจำนวนลูกหลานที่เก็บไว้ด้วย กล่าวคือหาก LP มีขนาด size(LP) แล้ว จะได้ว่า size(Ladder) เท่ากับ 2 × size(LP) ยกเว้นในกรณีที่บรรพบุรุษขึ้นไปถึงรากของต้นไม้ ซึ่งในกรณีนั้นจะมีสมาชิกน้อยกว่า 2 × size(LP)
จากการเก็บข้อมูลแบบนี้ สังเกตว่าหากเริ่มต้นที่จุดยอด v ซึ่ง Ladder ของ v มีขนาดดั้งเดิม h เมื่อผ่านการเพิ่มจุดยอดบรรพบุรุษแล้วก็จะมีขนาด 2h แทน กรณีเลวร้ายมากสุดในการกระโดดก็คือขณะนี้กำลังอยู่ที่รากของต้นไม้ย่อย ซึ่งจะทำให้กระโดดได้เพียง h ขั้น ในรอบที่สอง แน่นอนว่า Ladder ของจุดยอดที่กำลังอยู่ต้องมีขนาดดั้งเดิมมากกว่าหรือเท่ากับ 2h แน่นอน เมื่อเพิ่มจุดยอดบรรพบุรุษเข้าไปแล้วก็จะทำให้มีขนาดเป็น 4h เช่นเดียวกันกับรอบที่แล้ว กรณีเลวร้ายมากที่สุดก็คือขึ้นไปได้เพียง 2h และในรอบต่อ ๆ ไปอย่างเลวร้ายที่สุดก็จะขึ้นได้ 4h 8h 16h ไปเรื่อย ๆ และจากที่ h มีค่าน้อยสุดคือ 1 จึงทำให้สรุปได้ว่าการกระโดดโดยรวมจะใช้เวลาเพียง O(log n)

ขั้นตอนวิธีบันได

ขั้นตอนวิธีนี้รวม 'ขั้นตอนวิธีตัวชี้กระโดด' และ 'การแยกส่วนของบันได' เข้าด้วยกัน โดยสังเกตว่าจากการกระโดดหนึ่งครั้งของ 'ขั้นตอนวิธีตัวชี้กระโดด' ไปที่จุดยอด z ไป 2ᵖ ขั้น จะเหลือการกระโดดอีกไม่ถึง 2ᵖ ขั้นเช่นกันเพื่อที่จะไปถึงจุดยอดเป้าหมาย และจากการที่เพิ่งกระโดดขึ้นมา 2ᵖ ขั้น Ladder ของ z ก็จะมีขนาดมากกว่าหรือเท่ากับ 2ᵖ ทำให้ Ladder ของ z นี้เก็บข้อมูลของจุดยอดปลายทางกับจุดยอด z ไว้ในแถวลำดับเดียวกันอย่างแน่นอน ดังนั้นจึงสามารถตอบคำถามนี้ได้ในเวลา O(1)