مجاميع البادئة: حساب مجموع نطاق بطرح حدين مع بداية مشمولة

ماذا يخزن حد البادئة؟

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

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

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

ابن جدولًا من ست قيم معلنة

قيمنا من الموضع صفر إلى خمسة هي 5 ثم سالب 2 ثم صفر ثم 7 ثم سالب 4 ثم 3. نبدأ بالمجموع صفر، ونضيف 5 فيصبح أول مجموع بعد عنصر واحد 5. نضيف سالب 2 فنصل إلى 3 بعد عنصرين. إضافة الصفر تبقي 3، ثم إضافة 7 تجعل المجموع 10، وبعد سالب 4 يصبح 6، وبعد 3 يصبح 9.

جدول الحدود من صفر إلى ستة يحمل إذن 0 و5 و3 و3 و10 و6 و9. الرسم الرئيسي يضع صف القيم منفصلًا من صف مجاميع الحدود، لأن العددين متداخلان في الشكل لكنهما لا يصفان المواضع نفسها. قيمة 10 عند الحد أربعة جمعت العناصر من الموضع صفر حتى ثلاثة، ومنها 7، ولا تشمل سالب 4 عند الموضع أربعة.

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

لماذا يحسب طرح حدين المجموع المطلوب؟

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

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

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

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

البداية مشمولة والتوقف غير مشمول

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

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

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

النطاق الفارغ والمفرد والكامل

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

النطاق الكامل يبدأ عند صفر ويتوقف عند ستة، فيكون المجموع 9 ناقص صفر، أي 9. والنطاق الذي يضم العنصر عند أربعة وحده يبدأ عند أربعة ويتوقف عند خمسة، فيكون 6 ناقص 10، أي سالب 4. هذه حالة مفردة تبين أيضًا أن طرح المجاميع ليس طرح الأكبر من الأصغر تلقائيًا؛ ترتيب الحدين هو الذي يحدد العملية.

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

الصفر والسالب يغيران قراءة الجدول

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

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

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

كود أصلي يثبت نوع القيم وعقد الحدود

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

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

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

def prefix_totals(values):
    totals = [0]
    for value in values:
        if type(value) is not int:
            raise TypeError("integer values required")
        totals.append(totals[-1] + value)
    return tuple(totals)


def range_total(totals, start, stop):
    if type(start) is not int or type(stop) is not int:
        raise TypeError("integer boundaries required")
    if not totals or totals[0] != 0:
        raise ValueError("use prefix_totals output")
    length = len(totals) - 1
    if not 0 <= start <= stop <= length:
        raise ValueError("invalid half-open range")
    return totals[stop] - totals[start]

مرجع مكتبي للحساب التراكمي

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

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

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

[1]

تغيير عنصر يجعل بعض المجاميع قديمة

نبني جدول الأصل ثم نغير قيمة الموضع ثلاثة من 7 إلى 9. الفرق في هذا العنصر وحده يساوي 2. المجاميع قبل دخوله تبقى صفرًا و5 و3 و3، لكن الحد أربعة يصبح 12 بدل 10، والحد خمسة يصبح 8 بدل 6، والحد ستة يصبح 11 بدل 9. كل بادئة تحتوي العنصر المعدل زادت بمقدار الفرق نفسه.

النطاق من واحد إلى خمسة يصبح مجموعه 8 ناقص 5، أي 3، بينما الجدول القديم سيجيب 6 ناقص 5، أي 1. ليس هذا خطأ في الطرح؛ إنه استعمال لقطة قديمة على سؤال عن قيم جديدة. نراجع هوية نسخة القيم والجدول معًا، ولا نحكم أن تحديث القائمة الأصلية حدث تلقائيًا داخل حاوية أعداد بنيت منها سابقًا.

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

الإلحاق والترتيب يغيران سؤال النطاق

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

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

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

ما الذي اختصرناه في الاستعلامات المتكررة؟

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

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

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

يمكن استعادة القيم من جميع الحدود

إذا حفظنا جدول البادئة كاملًا لهذه الأعداد، نستطيع استعادة كل عنصر بطرح الحد السابق من التالي. فروق جدولنا المتجاورة تعيد 5 وسالب 2 وصفرًا و7 وسالب 4 و3. لذلك لا يصح وصف الجدول الكامل بأنه أبقى المجموع النهائي فقط؛ هو يحفظ معلومات أكثر تسمح بإعادة هذه القيم في ترتيبها ضمن العقد الحسابي الذي استعملناه.

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

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

فحوص تقارن كل نطاق بجمع مباشر

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

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

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

بطاقة جدول تربط الحدود بنسخة القيم

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

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

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