Binary Indexed Tree หรือ Fenwick Tree ใน C ++?

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

เมื่อพิจารณาถึงอาร์เรย์แบบฐานเดียว ต้นไม้ Fenwick จะเข้าใจได้ง่ายที่สุด แต่ละองค์ประกอบที่มีดัชนี j คือกำลัง 2 มีผลรวมขององค์ประกอบ j แรก องค์ประกอบที่มีดัชนีระบุผลรวมของกำลังสอง (แตกต่าง) ของ 2 ประกอบด้วยผลรวมขององค์ประกอบตั้งแต่ยกกำลัง 2 โดยทั่วไปแล้ว องค์ประกอบแต่ละองค์ประกอบประกอบด้วยผลรวมของค่าตั้งแต่พาเรนต์ในทรี และพาเรนต์นั้นคือ พบได้โดยการล้างบิตต่ำสุดหรือมีความสำคัญน้อยที่สุดในดัชนี

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

ตัวอย่างเช่น ให้บุคคลหนึ่งประสงค์จะคำนวณผลรวมของค่าสิบเอ็ดค่าแรก Eleven คือ 1,011 ในรูปแบบเลขฐานสอง ประกอบด้วย 1 บิต 3 ตัว ดังนั้นต้องเพิ่มองค์ประกอบ 3 อย่าง ได้แก่ 1000, 1010 และ 1011 ซึ่งประกอบด้วยผลรวมของค่า 1-8, 9-10 และ 11 ตามลำดับ

การใช้งาน C อย่างง่ายมีดังนี้

ตัวอย่าง

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the minimum or least significant one
int A1[SIZE];
int sum(int i) // Returns the sum from index 1 to i{
   int sum = 0;
   while (i > 0)
   sum += A1[i], i -= LSB(i);
   return sum;
}
void add(int i, int k) // Adds k to element with index i{
   while (i < SIZE)
   A1[i] += k, i += LSB(i);
}