ต้นไม้เฟนวิก

ในวิทยาการคอมพิวเตอร์ ต้นไม้เฟนวิก (อังกฤษ: Fenwick tree) หรืออาจเรียกว่า binary indexed tree เป็นโครงสร้างข้อมูลที่ใช้ในการคำนวณผลรวมนำหน้า (prefix sum) ของตารางข้อมูลได้อย่างมีประสิทธิภาพ โครงสร้างข้อมูลนี้คิดค้นโดย Peter Fenwick ใน พ.ศ. 2537^[1]

การคำนวณผลรวมนำหน้าอย่างง่ายก็คือการสร้างตารางคำนวณผลลัพธ์ล่วงหน้า ซึ่งใช้เวลา ${\displaystyle O(n)}$ ในการดำเนินการ และหลังจากนั้นก็สามารถหาผลลัพธ์จากตารางดังกล่าวได้ในเวลาเพียง ${\displaystyle O(1)}$ อย่างไรก็ตาม หากหลังจากนั้นต้องการที่จะแก้ไขข้อมูลขึ้นมา ก็ต้องคำนวณข้อมูลทั้งตารางใหม่อีกรอบ กล่าวคือหากมีการแก้ข้อมูล ${\displaystyle q}$ รอบ ก็จะทำให้ต้องเสียเวลา ${\displaystyle O(nq)}$ ซึ่งเสียเวลาเป็นอย่างมาก ต้นไม้เฟนวิกเข้ามาช่วยลดเวลาในส่วนนี้โดยทำให้การแก้ไขข้อมูลแต่ละครั้งใช้เวลาเพียง ${\displaystyle O(\log n)}$ ทำให้การแก้ข้อมูล ${\displaystyle q}$ รอบ ใช้เวลาเพียง ${\displaystyle O(q\log n)}$ แต่ก็แลกมากับเวลาในการหาผลลัพธ์ซึ่งเพิ่มขึ้นจาก ${\displaystyle O(1)}$ มาเป็น ${\displaystyle O(\log n)}$

อ้างอิง

1. Peter M. Fenwick (1994). "A new data structure for cumulative frequency tables". Software: Practice and Experience. 24 (3): 327–336. doi:10.1002/spe.4380240306.

แหล่งข้อมูลอื่น

• A tutorial on Fenwick Trees on TopCoder
• An article on Fenwick Trees on Algorithmist
• An entry on Fenwick Trees on Polymath wiki
• Order-statistics tree, a related data structure เก็บถาวร 2012-12-01 ที่ เวย์แบ็กแมชชีน