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

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

การคำนวณผลรวมนำหน้าอย่างง่ายก็คือการสร้างตารางคำนวณผลลัพธ์ล่วงหน้า ซึ่งใช้เวลา  ในการดำเนินการ และหลังจากนั้นก็สามารถหาผลลัพธ์จากตารางดังกล่าวได้ในเวลาเพียง  อย่างไรก็ตาม หากหลังจากนั้นต้องการที่จะแก้ไขข้อมูลขึ้นมา ก็ต้องคำนวณข้อมูลทั้งตารางใหม่อีกรอบ กล่าวคือหากมีการแก้ข้อมูล  รอบ ก็จะทำให้ต้องเสียเวลา  ซึ่งเสียเวลาเป็นอย่างมาก ต้นไม้เฟนวิกเข้ามาช่วยลดเวลาในส่วนนี้โดยทำให้การแก้ไขข้อมูลแต่ละครั้งใช้เวลาเพียง  ทำให้การแก้ข้อมูล  รอบ ใช้เวลาเพียง  แต่ก็แลกมากับเวลาในการหาผลลัพธ์ซึ่งเพิ่มขึ้นจาก  มาเป็น 

 อ้างอิง 

 แหล่งข้อมูลอื่น 
 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 

หมวดหมู่:ต้นไม้ (โครงสร้างข้อมูล)