شجرة فنويك

{

• while (i < SIZE)
• A[i] += k, i += LSB(i);
• }

فيما يلي تحقيق لشجرة فنويك بلغة سي

ومن ناحية أخرى، #define LSB(i) ((i) & -(i)) // يقوم هذا الماكرو بتصفير جميع البتات عدا البت الأقل أهمية

}

من جانب آخر، void add(int i, int k) // تقوم هذه الدالة بإضافة (كي) إلى العنصر (آي)

int A[SIZE];

وعلى صعيد آخر، int sum(int i) // i تعيد هذه الدالة مجموع كافة العناصر من صفر وحتى العنصر

{

int sum = 0;

• while (i > 0)
• sum += A[i], i -= LSB(i);
• return sum;

كيفية العمل

من جانب آخر، إن لشجرة فنويك بنيان شجري، وعلى الرغم من ذلك يتم تحقيق هذه الشجرة بشكل مضمّن في مصفوفة أحادية البعد بشكل مماثل لتحقيق شجرة الكومة. يتم حساب والد أو ابن عنصر ما عن طريق التلاعب ببتات ذلك العنصر. يحتوي كل عنصر من المصفوفة على مجموع مجال ما من الأعداد، وعن طريق إضافة مجاميع العقد الآباء وصولاً إلى جذر الشجرة يتم حساب مجموع كل المجالات المتتالية وبالتالي نحصل على مجموع كافة العناصر وصولاً إلى ذلك العنصر. عند تعديل قيمة ما من المصفوفة، يتم تعديل كل مجاميع المجالات المتضمنة ذلك العنصر من خلال القيام باجتياز عمودي للشجرة شبيه بالاجتياز المشروح سابقاً. يتم وضع مجاميع المجالات الجزئية ضمن عقد الشجرة المختلفة بطريقة يمكن من القيام بحساب مجاميع البوادئ وتعديل عناصر المجموعة بنفس التعقيد الزمني(تعقيد حالةٍ أسواً ).

التحقيق