شجرة فينويك للمجاميع المتغيرة: مسار التعديل وفرق الاستبدال

من جدول ثابت إلى سؤال بعد تعديل

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

سنراجع هذا السؤال بقائمة مؤلفة من ثمانية أعداد صحيحة، وبكود صغير يخزن القيم الحالية ومجاميع كتل محددة. نستخدم اسم شجرة فينويك، أو الشجرة الثنائية المفهرسة، للمنهج المعروف الذي نطبقه؛ يوضح مرجع CP-Algorithms قاعدة حركة الخلايا الداخلية، ويعرض دليل USACO استعمال البنية لتحديث موضع والاستعلام عن مجموع نطاق. أما الأعداد ومسارات تعديلها والفحوص في هذا الشرح فهي أمثلة مؤلفة لهذا المقال.

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

مرجع حركة الخلايا، مرجع تحديث الموضع ومجموع النطاق.

ثمانية مواضع وخلايا من واحد

قيم الأصل بحسب المواضع من صفر إلى سبعة هي 4 وسالب 1 و 6 وصفر و 3 وسالب 2 و 5 و 1. مجموعها الكامل يساوي 16. يستعمل القارئ الخارجي مواضع تبدأ من صفر، لكن خلايا البنية الداخلية تبدأ من واحد. لذلك يناظر الموضع صفر الخلية واحد، ويناظر الموضع أربعة الخلية خمسة. هذا التحويل جزء من التنفيذ، ولا يعني إضافة عنصر جديد إلى الأصل.

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

خلايا الأصل من واحد إلى ثمانية تحمل 4 و 3 و 6 و 9 و 3 و 1 و 5 و 16. ليست هذه جميع مجاميع البادئة. الخلية ثلاثة مثلًا تحمل 6 وحده، لا مجموع أول ثلاثة عناصر الذي يساوي 9. سنفسر سبب ذلك بتغطية كل خلية، ونراجع الخلايا بالجمع المباشر للأجزاء التي تمثلها قبل استعمالها في أي استعلام.

طول الكتلة يحدده البت الأخير

في ترقيمنا الداخلي نأخذ آخر بت يساوي واحدًا في رقم الخلية، ونستخرج قيمته بعملية منخفض البت المكتوبة في الكود على الصورة cell & -cell. نستعمل هذه القيمة طولًا لكتلة تنتهي عند الخلية نفسها. الخلية ستة مثلًا طول كتلتها اثنان، والخلية أربعة طول كتلتها أربعة، والخلية سبعة طول كتلتها واحد. المقصود هنا أرقام الخلايا الموجبة، لا قيم البيانات التي يمكن أن تكون سالبة.

يمكن كتابة تغطية الخلية الداخلية i على هيئة مواضع خارجية من i ناقص طول الكتلة إلى ما قبل i. لذلك تغطي الخلية ستة الموضعين أربعة وخمسة؛ قيمتاهما 3 وسالب 2، ومجموعهما 1. وتغطي الخلية أربعة المواضع صفر وواحد واثنين وثلاثة، فتحمل 4 ناقص 1 زائد 6 زائد صفر، أي 9. أما الخلية سبعة فتغطي الموضع ستة وحده فتحمل 5.

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

جمع أول سبعة عناصر بثلاث خلايا

نعرّف prefix عند التوقف سبعة بأنه مجموع العناصر قبل الموضع سبعة، أي المواضع صفر حتى ستة. نبدأ داخليًا بالخلية سبعة فنقرأ 5، ثم نطرح طول كتلتها واحدًا فيصبح رقم الخلية ستة. نقرأ من ستة قيمة 1، ثم نطرح طول كتلتها اثنين فننتقل إلى أربعة. نقرأ 9 من أربعة، ثم نطرح أربعة فنصل إلى الصفر ونتوقف.

المجموع المطلوب إذن 5 زائد 1 زائد 9، أي 15. تغطي الكتل الثلاث الموضع ستة وحده، ثم أربعة وخمسة، ثم صفر إلى ثلاثة. لا يوجد عنصر مكرر بينها، ولا فراغ في أول سبعة مواضع. الخلية الثامنة خارج هذه القراءة، لأن قيمة الموضع سبعة الأخير ليست ضمن الطلب. مجموع القائمة كاملة سيكون 16، لكنه يجيب حدًا آخر هو ثمانية.

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

نطاق نصف مفتوح يحتاج بادئتين

نعطي range_sum بداية مشمولة وتوقفًا غير مشمول. طلب البداية اثنين والتوقف سبعة يشمل المواضع اثنين وثلاثة وأربعة وخمسة وستة. قيمها 6 وصفر و 3 وسالب 2 و 5، ومجموعها 12. للحصول عليه من البنية نطرح مجموع ما قبل اثنين من مجموع ما قبل سبعة. البادئة عند اثنين تساوي 3، وعند سبعة تساوي 15، والفرق 12.

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

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

إضافة أربعة في الموضع الرابع

ننادي add للموضع أربعة بفرق مقداره 4. قيمة هذا الموضع كانت 3، فتصبح 7. يبدأ مسار التعديل بالخلية خمسة لأن الترقيم الداخلي يزيد واحدًا. نزيد الخلية خمسة أربعة، ثم نضيف طول كتلتها واحدًا إلى رقمها فنصل إلى ستة. نزيد الخلية ستة أربعة، ثم نضيف اثنين فنصل إلى ثمانية. نزيد ثمانية أربعة، ثم ينتقل المسار إلى ستة عشر، خارج البنية، فيتوقف.

الخلايا التي زارتها العملية هي خمسة وستة وثمانية. تتحول قيمها من 3 و 1 و 16 إلى 7 و 5 و 20، وتبقى الخلايا الأخرى كما كانت. نراجع التغطية: الخامسة تمثل الموضع أربعة وحده، والسادسة تضم أربعة وخمسة، والثامنة تضم القائمة كلها. جميعها تحتوي العنصر المعدل، بينما الخلية أربعة تغطي مواضع سابقة لا يدخل بينها أربعة، فلا ينبغي تغيير مجموعها 9.

تعيد دالة الإضافة مسار الخلايا بوصفه أثرًا للمراجعة، لا قائمة جميع البادئات التي تغيرت. بعض حدود البادئة اللاحقة تتغير نتيجتها رغم أننا لا نخزن كل واحد منها منفردًا. هذا الفرق هو ما نريد رؤيته: عدلنا ثلاث خلايا كتل في المثال، وستجمع الاستعلامات المقبلة هذه الخلايا بحسب حدودها الجديدة.

الاستعلام بعد الإضافة يقرأ النسخة الجديدة

نعيد قراءة البادئة عند سبعة بعد الإضافة، فنمر بالخلايا سبعة وستة وأربعة كما مررنا قبلها. الخلية سبعة ما زالت 5، والخلية ستة صارت 5 بدل 1، والخلية أربعة ما زالت 9. المجموع الجديد 19. تغيير القيم المخزنة في المسار المعني جعل الاستعلام نفسه يجيب عن الحالة الجديدة دون أن نغير حد التوقف أو نعيد بناء جميع الخلايا.

البادئة عند اثنين بقيت 3، لأنها لا تشمل موضع التعديل. لذلك صار نطاق اثنين إلى ما قبل سبعة يساوي 19 ناقص 3، أي 16. بالجمع المباشر للقيم الحالية نجد 6 وصفر و 7 وسالب 2 و 5، ومجموعها 16 أيضًا. أما النطاق صفر إلى ما قبل أربعة فبقي 9؛ وقوع التغيير بعده يعني أنه لا يدخل في سؤاله.

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

الاستبدال باثنين يرسل فرقًا سالبًا

نواصل على الحالة التي زاد فيها الموضع أربعة إلى 7، ثم نطلب replace للموضع اثنين بالقيمة 2. قيمته الحالية 6، ولذلك فرق الاستبدال يساوي 2 ناقص 6، أي سالب 4. إذا أرسلنا 2 إلى add بدل الفرق فسوف نزيد 6 إلى 8، وهذا لا يحقق طلب الاستبدال. لهذا يحتفظ الكائن بالقيمة الحالية حتى يحسب الفرق قبل نشره في الخلايا.

الموضع اثنان يبدأ داخليًا بالخلية ثلاثة. نزيدها سالب 4، ثم ينتقل المسار إلى أربعة ثم ثمانية. تتغير الخلية ثلاثة من 6 إلى 2، والرابعة من 9 إلى 5، والثامنة من 20 إلى 16. تبقى الخامسة 7 والسادسة 5 لأن كتلتاهما لا تحتويان الموضع اثنين. القائمة الحالية أصبحت 4 وسالب 1 و 2 وصفر و 7 وسالب 2 و 5 و 1.

البادئة عند سبعة الآن تساوي 5 زائد 5 زائد 5، أي 15. والنطاق من اثنين إلى ما قبل سبعة يساوي 15 ناقص 3، أي 12. عاد الرقمان إلى نتائج الأصل، لكن القيم الداخلية والأصلية لم تعد كما كانت. توافق مجموع نطاق لا يثبت تطابق قائمتين؛ فقد عوضت زيادة أربعة في موضع انخفاض أربعة في موضع آخر.

عرض الرسم بالحجم الكامل

السالب والصفر وحدود غير صالحة

قيم البيانات في هذا التنفيذ أعداد صحيحة، ويمكن أن تكون سالبة أو صفرًا. الإضافة بفرق سالب تقلل القيمة، والاستبدال بالقيمة الحالية يولد فرقًا صفرًا. تنفذ عملية الفرق الصفري مسار الخلايا نفسه وتترك مجاميعها دون تغيير. لا نستنتج من السالب أن الفهرس سالب، لأن نوع الرقم ودوره مختلفان: الفهرس يختار مكانًا صالحًا، والفرق يحدد مقدار التغير فيه.

نرفض فهرس إضافة خارج المواضع، ومنها سالب واحد وثمانية في قائمة الثمانية. لكن التوقف ثمانية صالح للبادئة لأنه حد بعد آخر عنصر، والتوقف صفر صالح للبادئة الفارغة. كما نرفض بداية أكبر من التوقف في سؤال نطاق. هذه الفروق ليست استثناءات حسابية اعتباطية؛ إنها نتيجة تعريف الموضع بأنه عنصر، والحد بأنه عدد عناصر سبقته.

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

كود يصرح بالقيم والكتل والعمليات

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

تقدم add فرقًا إلى موضع، وتقدم replace قيمة نهائية يحولها الكود إلى فرق. وتقرأ prefix مجموع ما قبل حد توقف، بينما range_sum تقبل حدودًا نصف مفتوحة. تعيد snapshot نسختين غير قابلتين للتعديل المباشر: القيم الحالية والخلايا الداخلية. الغرض منهما أن يرى الاختبار ما حدث، لا أن يعتمد المستخدم على تغيير هذه الصور لإجراء تحديث جديد.

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

class MutableRangeSums:
    def __init__(self, values):
        values = tuple(values)
        if any(type(value) is not int for value in values):
            raise TypeError("integer values required")
        self._values = list(values)
        self._blocks = [0] * (len(values) + 1)
        for index, value in enumerate(values):
            self._propagate(index, value)

    def _propagate(self, index, delta):
        cell = index + 1
        visited = []
        while cell < len(self._blocks):
            self._blocks[cell] += delta
            visited.append(cell)
            cell += cell & -cell
        return tuple(visited)

    def _check_index(self, index):
        if type(index) is not int:
            raise TypeError("integer index required")
        if not 0 <= index < len(self._values):
            raise IndexError(index)

    def add(self, index, delta):
        self._check_index(index)
        if type(delta) is not int:
            raise TypeError("integer delta required")
        self._values[index] += delta
        return self._propagate(index, delta)

    def replace(self, index, value):
        self._check_index(index)
        if type(value) is not int:
            raise TypeError("integer value required")
        return self.add(index, value - self._values[index])

    def prefix(self, stop):
        if type(stop) is not int:
            raise TypeError("integer boundary required")
        if not 0 <= stop <= len(self._values):
            raise IndexError(stop)
        total = 0
        cell = stop
        while cell:
            total += self._blocks[cell]
            cell -= cell & -cell
        return total

    def range_sum(self, start, stop):
        if type(start) is not int or type(stop) is not int:
            raise TypeError("integer boundaries required")
        if not 0 <= start <= stop <= len(self._values):
            raise IndexError((start, stop))
        return self.prefix(stop) - self.prefix(start)

    def snapshot(self):
        return tuple(self._values), tuple(self._blocks)

لماذا يتحرك الاستعلام إلى اليسار والتعديل إلى أعلى؟

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

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

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

مرجع قائمة مباشرة بعد كل عملية

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

جربنا 1093 قائمة ممكنة من أعداد سالب 2 وصفر و 3، بأطوال من صفر إلى ستة. نفذنا عليها بالتتابع 12030 عملية إضافة واستبدال، وأجرينا 334612 مقارنة لنطاقات. راجعنا أيضًا كل خلية داخلية بمجموع جزء القائمة الذي يجب أن تغطيه، وكل بادئة بجمع مباشر. هذا يفحص علاقة التخزين بالقيم الحالية، وليس فقط مجموعة أرقام اختيرت لموافقة الرسم.

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

لقطة النتيجة ومسؤولية تعريف النسخة

لقطة الأصل تحمل قيمًا مجموعها 16 وخلايا تنتهي بالعدد نفسه. وبعد الإضافة أصبح المجموع 20، وبعد الاستبدال عاد إلى 16. من المهم حفظ ترتيب العمليات: الاستبدال شرحناه بعد الإضافة، لا على نسخة مستقلة من الأصل. إذا نفذ القارئ الاستبدال وحده من الأصل سيحصل على مجموع 12، وهذا نتيجة صحيحة لتجربة مختلفة، ولا يناقض مجموع الحالة المتتابعة التي عرضناها.

يمكن وصف الطلب ببطاقة قصيرة: ثمانية أعداد صحيحة بالترتيب المعلن، مواضع خارجية تبدأ من صفر، خلايا داخلية تبدأ من واحد، وحدود نطاق ببداية مشمولة وتوقف غير مشمول. نضيف عملية الموضع أربعة بفرق 4 ثم عملية الموضع اثنين بقيمة نهائية 2. تحفظ هذه البطاقة الفرق بين add و replace، وتفسر لماذا زارت كل واحدة خلايا مختلفة.

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