شجرة Fenwick للمجاميع السابقة
تحديث نقطة واستعلام مجموع سابق في log n
شجرة Fenwick للمجاميع السابقة درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
لماذا تفشل مصفوفات البادئات
تجيب مصفوفة مجموع البادئة العادية عن النطاقات فورًا، لكن تحديثًا واحدًا يجبرك على إعادة بنائها. ومع كثرة التحديثات، يصبح ذلك بطيئًا. ⏱️
إليك شجرة Fenwick
تدعم شجرة Fenwick، أو BIT، كلًا من تحديثات النقاط واستعلامات البادئة في O(log n). وهي خيارك المفضّل للمجاميع التراكمية الديناميكية.
الفهرسة بدءًا من واحد حسب التصميم
تعيش شجرة Fenwick في مصفوفة مفهرسة بدءًا من 1. نستخدم الفهرس 0 كقيمة حارسة صامتة، لذلك تبدأ كل بياناتك الفعلية عند الموضع 1.
tree = [0] * (n + 1)سحر أقل بت مضبوط
يغطي كل فهرس كتلة من القيم. ويساوي حجم الكتلة i & -i، أي أقل بت مضبوط في i. وهذه الحيلة الواحدة هي أساس الشجرة بأكملها.
lowbit = i & -iتحديث نقطة واحدة
لإضافة قيمة عند الموضع i، انتقل إلى الأمام بمقدار lowbit في كل خطوة، ولمس كل كتلة تحتوي على i.
while i <= n:
tree[i] += delta
i += i & -iالاستعلام عن مجموع بادئة
لجمع أول i من القيم، تحرّك إلى الخلف واطرح lowbit في كل خطوة حتى تصل إلى الصفر.
s = 0
while i > 0:
s += tree[i]
i -= i & -iكلتا الحلقتين لوغاريتميتان
تزيل كل حلقة بتًا واحدًا في كل تكرار، لذا تعمل بحد أقصى log n مرة. ولهذا يظل كل من التحديث والاستعلام سريعًا.
مجموع نطاق من بادئتين
هل تريد المجموع من l إلى r؟ احسب prefix(r) ناقص prefix(l-1)، تمامًا كما في مصفوفة بادئة ثابتة، لكن التحديثات أصبحت رخيصة أيضًا.
range_sum = query(r) - query(l - 1)بناء الشجرة
أبسط طريقة للبناء هي استدعاء update لكل قيمة ابتدائية. تبلغ كلفتها O(n log n)، وهي سريعة بما يكفي لمعظم المسابقات.
for i, v in enumerate(a, 1):
update(i, v)استهلاك ضئيل للذاكرة
تحتاج شجرة Fenwick إلى مصفوفة واحدة فقط بحجم n+1. ويُعد هذا الحجم المدمج أحد أسباب انتشارها الكبير في المسابقات. 💾
متى تستخدم BIT
اختر شجرة Fenwick عندما تتناوب تحديثات النقاط مع استعلامات مجموع البادئة أو مجموع النطاق. فهي قصيرة الشيفرة ويصعب التفوق عليها.
اختبار سريع
لِنرسّخ طريقة تحرّك الحلقتين.
مراجعة: أساسيات BIT
تعرّفت إلى شجرة Fenwick: مفهرسة بدءًا من 1، ومدعومة بـ i & -i، مع تحديث نقطة واستعلام بادئة، وكلاهما في O(log n). بعد ذلك سنستخدمها لعدّ الانقلابات. 🎯
الأسئلة الشائعة
هل درس «شجرة Fenwick للمجاميع السابقة» مجاني؟
نعم — نص درس «شجرة Fenwick للمجاميع السابقة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «شجرة Fenwick للمجاميع السابقة»؟
تحديث نقطة واستعلام مجموع سابق في log n تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «شجرة Fenwick للمجاميع السابقة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- شجرة Fenwick للمجاميع السابقة
- الانقلابات باستخدام BIT
- شجرة المقاطع: الإنشاء والاستعلام
- الانتشار الكسول لتحديثات النطاق