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

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

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

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

• 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 ที่ เวย์แบ็กแมชชีน