شجرة فنويك
{{Infobox data structure}}
'''شجرة فنويك''' أو الشجرة الثنائية المفهرسة هي [[بنية بيانات|بنية معطيات]] يمكن فيها القيام بتعديل عنصر وحساب مجاميع البوادئ في جدول من القيم الحسابية [[تعقيد الوقت|بطريقة فعالة]].

اقترح بوريس ريابكو عام 1989 بنية المعطيات هذه<ref>{{استشهاد بدورية محكمة |مؤلف=بوريس ريابكو |عنوان=A fast on-line code. |صحيفة=Soviet Math. Dokl.  |المجلد=39 |العدد=3 |سنة=1989 |صفحات=533–537|مسار=http://boris.ryabko.net/dan1989.pdf | مسار أرشيف = https://web.archive.org/web/20190717074430/http://boris.ryabko.net/dan1989.pdf | تاريخ أرشيف = 17 يوليو 2019 }}</ref>، ثم أضاف إليها مجموعة من التنقيحات عام 1992<ref>{{استشهاد بدورية محكمة |مؤلف=بوريس ريابكو |عنوان=A fast on-line adaptive code|صحيفة=IEEE Trans.on Inform.Theory |المجلد=28 |العدد=1 |سنة=1992 |صفحات=1400–1404  |مسار=http://boris.ryabko.net/ryabko1992.pdf| مسار أرشيف = https://web.archive.org/web/20190714141801/http://boris.ryabko.net/ryabko1992.pdf | تاريخ أرشيف = 14 يوليو 2019 }}</ref>، ولكنها حظيت بشهرة واسعة تحت اسم شجرة فنويك بعدما نشر بيتر فنويك شرحاً مفصلاً عنها في ورقة بحثية عام 1994.<ref>{{استشهاد بدورية محكمة |مؤلف=بيتر فنويك |عنوان=A new data structure for cumulative frequency tables |صحيفة=Software: Practice and Experience |المجلد=24 |العدد=3 |سنة=1994 |صفحات=327–336 |doi=10.1002/spe.4380240306 |citeseerx=10.1.1.14.8917 |مسار=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8917&rep=rep1&type=pdf| مسار أرشيف = https://web.archive.org/web/20150531060905/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8917&rep=rep1&type=pdf | تاريخ أرشيف = 31 مايو 2015 }}</ref>

بالمقارنة مع مصفوفة أحادية البعد تستطيع شجرة فنويك الموازنة بين عملية تعديل العنصر وحساب مجاميع البودائ بطريقة أفضل. في مصفوفة أحادية البعد مكونة من <math>n</math> عنصر يمكن تخزين العناصر أو مجاميع البوادئ وليس كلا القيمتين. في الحالة الأولى (تخزين العناصر) يستهلك حساب مجاميع البوادئ [[تعقيد الوقت#/الوقت الخطي|وقتاً خطياً]] <math>O(n)</math>، وفي الحالة الثانية (تخزين مجاميع البوادئ) يستهلك تخزين عنصر ما في المصفوفة وقتاً خطياً، أي أنه في كلا الحالتين تستهلك إحدى العمليتين وقتاً خطياً. تسمح شجرة فنويك بالقيام بكلا العمليتين خلال [[تعقيد الوقت#/وقت لوغاريتمي|وقت لوغارتمي]] <math>O(\log n)</math>. يتم ذلك من خلال تمثيل عناصر المصفوفة [[شجرة (بنية بيانات)|كبنية شجرية]]، في هذه البنية الشجرية تُخزن في كل عقدة مجموع عناصر عقد الشجرة المتفرعة منها. تسمح هذه البنية الشجرية بتنفيذ العمليات المذكورة أعلاه عن طريق زيارة عدد من العقد مقداره <math>O(\log n)</math>.

== كيفية العمل ==

إن لشجرة فنويك بنيان شجري، وعلى الرغم من ذلك يتم تحقيق هذه الشجرة بشكل مضمّن في [[مصفوفة (حوسبة)|مصفوفة أحادية البعد]] بشكل مماثل لتحقيق [[الكومة (بنية معطيات)|شجرة الكومة]]. يتم حساب والد أو ابن عنصر ما عن طريق التلاعب ببتات ذلك العنصر. يحتوي كل عنصر من المصفوفة على مجموع مجال ما من الأعداد، وعن طريق إضافة مجاميع العقد الآباء وصولاً إلى جذر الشجرة يتم حساب مجموع كل المجالات المتتالية وبالتالي نحصل على مجموع كافة العناصر وصولاً إلى ذلك العنصر. عند تعديل قيمة ما من المصفوفة، يتم تعديل كل مجاميع المجالات المتضمنة ذلك العنصر من خلال القيام [[شجرة (بنية بيانات)#/طرق الاجتياز|باجتياز عمودي]] للشجرة شبيه بالاجتياز المشروح سابقاً. يتم وضع مجاميع المجالات الجزئية ضمن عقد الشجرة المختلفة بطريقة يمكن من القيام بحساب مجاميع البوادئ وتعديل عناصر المجموعة بنفس التعقيد الزمني(تعقيد حالةٍ أسواً <math>O(\log n)</math>).

== التحقيق ==
فيما يلي تحقيق لشجرة فنويك بلغة سي
<syntaxhighlight lang="C">
#define LSB(i) ((i) & -(i)) // يقوم هذا الماكرو بتصفير جميع البتات عدا البت الأقل أهمية

int A[SIZE];

int sum(int i) // i تعيد هذه الدالة مجموع كافة العناصر من صفر وحتى العنصر
{
    int sum = 0;
    while (i > 0) 
        sum += A[i], i -= LSB(i);
    return sum;
}
 
void add(int i, int k) // تقوم هذه الدالة بإضافة (كي) إلى العنصر (آي)
{
    while (i < SIZE) 
        A[i] += k, i += LSB(i);
}
</syntaxhighlight>

== المراجع ==
{{مراجع}}

{{علم الحاسوب - بنى شجرية}}
{{شريط بوابات|علم الحاسوب}}
{{روابط شقيقة|commons=Fenwick trees}}

[[تصنيف:أشجار (بنى معطيات)]]
[[تصنيف:اختراعات روسية]]
[[تصنيف:اختراعات سوفيتية]]
شجرة فنويك أو الشجرة الثنائية المفهرسة هي بنية معطيات يمكن فيها القيام بتعديل عنصر وحساب مجاميع البوادئ في جدول من القيم الحسابية بطريقة فعالة.

اقترح بوريس ريابكو عام 1989 بنية المعطيات هذه، ثم أضاف إليها مجموعة من التنقيحات عام 1992، ولكنها حظيت بشهرة واسعة تحت اسم شجرة فنويك بعدما نشر بيتر فنويك شرحاً مفصلاً عنها في ورقة بحثية عام 1994.

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

 كيفية العمل 

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

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

int A[SIZE];

int sum(int i) // i تعيد هذه الدالة مجموع كافة العناصر من صفر وحتى العنصر
{
    int sum = 0;
    while (i > 0) 
        sum += A[i], i -= LSB(i);
    return sum;
}
 
void add(int i, int k) // تقوم هذه الدالة بإضافة (كي) إلى العنصر (آي)
{
    while (i < SIZE) 
        A[i] += k, i += LSB(i);
}

 المراجع 

تصنيف:أشجار (بنى معطيات)
تصنيف:اختراعات روسية
تصنيف:اختراعات سوفيتية