جمع أي نطاق بالطرح

كان بناء مصفوفة المجموع التراكمي خطوةً تمهيدية. أما الآن فتأتي الفائدة الرائعة: الإجابة عن مجموع أي نطاق باستخدام عملية طرح واحدة. ⚡

مجموع النطاق ليس إلا مجموعًا كبيرًا ناقص مجموع أصغر. يؤدي طرح قيمتين من المجموع التراكمي إلى إلغاء كل ما يقع خارج نطاقك بوضوح.

لجمع العناصر من l إلى r، اطرح prefix[l] من prefix[r + 1]. تعمل هذه الصيغة الواحدة مع أي نطاق.

يحتوي prefix[r + 1] على كل شيء حتى r، بينما يحتوي prefix[l] على كل ما قبل l. ويترك الفرق الجزء الأوسط بالضبط.

بالنسبة إلى [3, 1, 4] يكون المجموع التراكمي هو [0, 3, 4, 8]. ولجمع الفهرسين 1 و2، اطرح 3 من 8 لتحصل على 5. وهذا يساوي 1 زائد 4.

كل استعلام هو عملية طرح واحدة فقط، لذا يُنفَّذ في O(1). وتستغرق ألفة استعلام الزمن نفسه لكل استعلام الذي يستغرقه استعلام واحد.

الخطأ الأكثر شيوعًا هو الفهرس عند الطرف الأعلى. مع وجود الصفر في البداية، تستخدم دائمًا prefix[r + 1]، وليس prefix[r]. انتبه إلى ذلك الحد.

حدّد مبكرًا ما إذا كان r مشمولًا. تتعامل هذه الصيغة مع النطاق باعتباره شاملًا لكل من l وr، وهذا ما تتوقعه معظم مسائل المسابقات.

تحافظ دالة مساعدة صغيرة على وضوح منطقك وتضع فهارسك في مكان واحد. اعتمد على هذه الدالة المساعدة بدلًا من كتابة العمليات الحسابية ضمنيًا.

لجمع المصفوفة بأكملها، استخدم l مساويًا لـ 0 وr مساويًا لـ n ناقص 1. تعطيك الصيغة prefix[n]، أي الإجمالي الكلي.

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

تريد حساب مجموع الفهارس من l إلى r، مع تضمين الطرفين.

يمكنك الآن الإجابة عن أي مجموع نطاق في O(1) باستخدام prefix[r + 1] ناقص prefix[l]. انتبه إلى الإزاحة الناتجة عن الصفر في البداية، وستتجنب الأخطاء. ✅