مصفوفات الفروق لتحديثات النطاق

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

تكلف إضافة قيمة إلى كل عنصر في نطاق، مع تكرار ذلك مرات كثيرة، O(n) لكل تحديث. ومع q من التحديثات، تتضخم هذه الكلفة بشدة.

بدلًا من تعديل كل خلية، سجّل فقط موضع بدء التغيير وموضع انتهائه. علّم الحافتين، لا الوسط.

تخزّن مصفوفة الفروق الفجوة بين كل عنصر والعنصر الذي يسبقه. ويؤدي تعديل فجوة واحدة إلى إزاحة مقطع كامل لاحقًا.

لإضافة v من l إلى r، أضف v عند الفهرس l واطرح v عند الفهرس r + 1. يغطي هذان التعديلان النطاق بأكمله.

تشغّل الإضافة عند l التغيير، بينما توقفه عملية الطرح عند r + 1. وبذلك تحدّدان التحديث في نطاق واحد، فتجعلانه متوقفًا بعده.

كل تحديث هو عمليتا كتابة فقط في المصفوفة، لذا تستغرق q من التحديثات O(q) إجمالًا. وتؤجَّل العمليات الثقيلة إلى النهاية.

بعد وضع جميع العلامات، احسب مجموعًا تراكميًا لمصفوفة الفروق. ويعيد هذا المرور الواحد بناء كل قيمة نهائية.

اجعل المصفوفة أطول بخلية واحدة حتى لا يتجاوز r + 1 نهايتها. وتتجنب خانة الحراسة الإضافية أخطاء الفهارس.

تنفق O(q) لوضع علامات التحديثات، ثم تمرّ مرورًا واحدًا زمنه O(n) لإعادة البناء. وتكون الكلفة المجمعة أقل بكثير من O(n مضروبًا في q) بالطريقة الساذجة.

تتألق مصفوفات الفروق في حسابات الحجوزات ورسوم الطرق، وفي أي مسألة تتضمن عمليات كثيرة من إضافة إلى نطاق ثم قراءة نهائية واحدة.

تضيف v إلى كل عنصر من الفهرس l إلى الفهرس r.

يمكنك تجميع تحديثات النطاق باستخدام مصفوفة فروق: علّم l وr + 1، ثم احسب المجموع التراكمي مرة واحدة لإعادة البناء. تحديثات سريعة وقراءة واحدة. ✅