الانتشار الكسول لتحديثات النطاق

ماذا لو طلب استعلام إضافة 5 إلى كل عنصر من l إلى r؟ إن لمس كل ورقة يستغرق O(n) لكل تحديث، وهو بطيء جدًا عند إجراء الكثير من تحديثات النطاق. 😰

يتيح Lazy propagation للعقدة تذكّر تغيير معلّق من دون دفعه إلى الأبناء بعد. ويُؤجَّل العمل حتى تحتاج فعليًا إلى هؤلاء الأبناء.

نحتفظ إلى جانب الشجرة بمصفوفة lazy. تخزّن lazy[node] تحديثًا ينطبق على النطاق الكامل لتلك العقدة، لكنه لم يُدفع إلى الأسفل بعد.

عندما يغطي التحديث عقدة بالكامل، عدّل قيمتها المخزّنة وراكم التغيير في lazy، ثم توقّف. لا حاجة إلى النزول أكثر.

قبل زيارة الأبناء، ادفع إلى الأسفل أي قيمة lazy معلّقة إلى كليهما. يحافظ ذلك على صحة الأبناء تمامًا عند قراءتهم.

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

لا يلمس تحديث النطاق إلا O(log n) عقدة، لأن العقد المغطاة بالكامل تتوقف مبكرًا. وهذه هي الفائدة الأساسية من استخدام التأجيل. ⚡

يجب أيضًا تمرير استعلامات النطاق إلى الأسفل قبل الاستدعاء التكراري، حتى تقرأ قيم الأبناء الأحدث. نسيان ذلك هو الخطأ الكلاسيكي في الانتشار الكسول.

بعد تحديث الأبناء، أعد دمج قيمة العقدة الأب اعتمادًا عليهم. يحافظ هذا الرفع على اتساق كل عقدة داخلية مع شجرتها الفرعية.

ينجح الانتشار الكسول مع العديد من العمليات، لكن الإسناد والجمع يندمجان بطريقة مختلفة. حدّد كيفية دمج تحديثين معلّقين قبل كتابة الكود.

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

ما الذي يجب أن يحدث قبل التكرار داخل أبناء العقدة؟

لقد تعلمت الانتشار الكسول: تخزين التغييرات المعلّقة، وتمريرها إلى الأسفل قبل النزول، ثم رفع القيم بعد ذلك، والحصول على تحديثات نطاق بتعقيد O(log n). 🎉