إتقان موضوع شجرة فنويك

شجرة فنويك أو الشجرة الثنائية المفهرسة هي بنية معطيات يمكن فيها القيام بتعديل عنصر وحساب مجاميع البوادئ في جدول من القيم الحسابية بطريقة فعالة.

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

بالمقارنة مع مصفوفة أحادية البعد تستطيع شجرة فنويك الموازنة بين عملية تعديل العنصر وحساب مجاميع البودائ بطريقة أفضل. في مصفوفة أحادية البعد مكونة من







n





{\displaystyle n}



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







O

(

n

)





{\displaystyle O(n)}



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







O

(

log

⁡

n

)





{\displaystyle O(\log n)}



. يتم ذلك من خلال تمثيل عناصر المصفوفة كبنية شجرية، في هذه البنية الشجرية تُخزن في كل عقدة مجموع عناصر عقد الشجرة المتفرعة منها. تسمح هذه البنية الشجرية بتنفيذ العمليات المذكورة أعلاه عن طريق زيارة عدد من العقد مقداره







O

(

log

⁡

n

)





{\displaystyle O(\log n)}



.