Range Sum Query

Q: ما هي مصفوفة المجاميع التراكمية؟

مصفوفة تكون فيها كل خانة هي مجموع جميع القيم التي تسبق موضعًا ما: prefix[i] = nums[0] + ... + nums[i-1] ، مع prefix[0] = 0 . تُنشئها في مرور واحد، ثم يكون مجموع أي نطاق [left, right] هو prefix[right+1] - prefix[left] .

Q: ما التعقيد الزمني لاستعلامات مجموع النطاق باستخدام المجاميع البادئة؟

O(n) لبناء مصفوفة البادئات مرة واحدة، ثم O(1) لكل استعلام، أي O(n + q) لـ q من الاستعلامات. جمع كل نطاق مباشرةً يكلّف ما يصل إلى O(n) لكل استعلام، و O(n·q) إجمالًا.

Q: ماذا لو أمكن أن تتغير المصفوفة بين الاستعلامات؟

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

سهلمجموع البادئات

+10

تحصل على مصفوفة من الأعداد الصحيحة nums لا تتغير، وقائمة من queries. كل استعلام هو زوج [left, right] من الفهارس التي يبدأ ترقيمها من 0، ويطلب حساب nums[left] + nums[left+1] + ... + nums[right]، مع تضمين الطرفين. أعد الإجابات بالترتيب نفسه الذي وردت به الاستعلامات.

الدالة

sumRange(nums: integer-array, queries: integer-2d-array) → integer-array

numsinteger-array: مصفوفة الأعداد الصحيحة، وهي نفسها لكل استعلام
queriesinteger-2d-array: النطاقات المراد جمعها، كلٌّ منها زوج [left, right] بحيث left ≤ right
تُرجعinteger-array: مجموع كل نطاق، واحد لكل استعلام، بترتيب الاستعلامات

القيود

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ queries.length ≤ 1500
0 ≤ left ≤ right < nums.length لكل استعلام [left, right]

أمثلة

المدخلات: nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
المخرجات: [6, 0, 1]
الشرح: تحتوي الفهارس من 0 إلى 2 على 3 + (-2) + 5 = 6. وتحتوي الفهارس من 1 إلى 4 على -2 + 5 + 1 + (-4) = 0. والنطاق [3, 3] هو القيمة المفردة 1.

المدخلات: nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
المخرجات: [18, 9, 2, 8]
الشرح: مجموع المصفوفة كلها هو 18، ومجموع القيمتين الأخيرتين هو 1 + 8 = 9، والفهرس 0 وحده هو 2، والفهرسان 1 إلى 2 مجموعهما 7 + 1 = 8.

سؤال إضافي

إذا كانت الأعداد تُشكّل شبكة وكان كل استعلام يطلب مجموع مستطيل، فكيف ستوسّع المجاميع البادئة للإجابة عن كل استعلام في زمن ثابت؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

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

اجمع كل نطاق

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

لكل استعلام، أضف nums[left] حتى nums[right] إلى المجموع. هذا صحيح لأنه يقرأ كل قيمة في النطاق، وبالنسبة إلى استعلام واحد فهذا أفضل ما يمكنك فعله. قد يمتد الاستعلام ليشمل ما يصل إلى n من القيم، لذا تتطلب q من الاستعلامات ما يصل إلى n × q عملية جمع: 1.5 × 10^7 عندما يكون n = 10^4 وq = 1500، ومعظم هذه العمليات مكررة تقريبًا.

الخوارزمية

أنشئ قائمة إجابات فارغة.
لكل استعلام [left, right]، عيّن total = 0.
أضف nums[i] إلى total لكل قيمة من i من left إلى right، شاملًا الطرفين.
ألحِق total بالإجابات، ثم أعدها بعد الاستعلام الأخير.

def sumRange(nums, queries):
    answers = []
    for left, right in queries:
        total = 0
        for i in range(left, right + 1):
            total += nums[i]
        answers.append(total)
    return answers

المجاميع البادئة

الفكرة

لتكن prefix[i] مجموع أول i من القيم، مع prefix[0] = 0. بالنسبة إلى [3, -2, 5, 1, -4, 6]، نحصل على [0, 3, 1, 6, 7, 3, 9].

النطاق [left, right] هو مجموع كل شيء حتى الفهرس right مطروحًا منه مجموع كل شيء قبل الفهرس left: prefix[right+1] - prefix[left]. بالنسبة إلى [1, 4]، يكون ذلك prefix[5] - prefix[1] = 3 - 3 = 0. تتيح القيمة 0 في البداية استخدام الصيغة نفسها لنطاق يبدأ عند الفهرس 0. تبني عملية مرور واحدة تتضمن n عمليات جمع المصفوفة، ثم يتطلب كل استعلام عملية طرح واحدة.

الخوارزمية

أنشئ prefix بطول n+1 مع prefix[0] = 0.
لكل i من 0 إلى n-1، عيّن prefix[i+1] = prefix[i] + nums[i].
لكل استعلام [left, right]، أضف prefix[right+1] - prefix[left] إلى الإجابات.
أعِد الإجابات.

def sumRange(nums, queries):
    # prefix[i] is the sum of the first i values, so prefix[0] = 0.
    prefix = [0] * (len(nums) + 1)
    for i, value in enumerate(nums):
        prefix[i + 1] = prefix[i] + value
    # nums[left..right] is the first right+1 values minus the first left values.
    return [prefix[right + 1] - prefix[left] for left, right in queries]

أخطاء شائعة وحالات حدّية

كتابة prefix[right] - prefix[left]. مع prefix[0] = 0، يؤدي ذلك إلى استبعاد nums[right]، لذا تُرجع النطاق [3, 3] القيمة 0 بدلًا من 1.
جعل prefix بطول nums، بحيث تتضمن prefix[i] القيمة nums[i]. عندئذٍ يحتاج النطاق الذي يبدأ عند 0 إلى prefix[-1]، وهو خارج النطاق، وتقرأ Python بصمت العنصر الأخير بدلًا منه.
إيقاف حلقة القوة الغاشمة عند i < right. كلا الطرفين مشمول، لذا لن يجمع [3, 3] أي شيء.
في Lua وR، اللتين تبدآن العد من 1، يغطي الاستعلام ذي الفهرسة التي تبدأ من 0 [left, right] القيم من nums[left+1] إلى nums[right+1]، وتتحرك فهارس البادئة بالطريقة نفسها.

أسئلة شائعة3

ما هي مصفوفة المجاميع التراكمية؟

مصفوفة تكون فيها كل خانة هي مجموع جميع القيم التي تسبق موضعًا ما: prefix[i] = nums[0] + ... + nums[i-1]، مع prefix[0] = 0. تُنشئها في مرور واحد، ثم يكون مجموع أي نطاق [left, right] هو prefix[right+1] - prefix[left].

ما التعقيد الزمني لاستعلامات مجموع النطاق باستخدام المجاميع البادئة؟

O(n) لبناء مصفوفة البادئات مرة واحدة، ثم O(1) لكل استعلام، أي O(n + q) لـ q من الاستعلامات. جمع كل نطاق مباشرةً يكلّف ما يصل إلى O(n) لكل استعلام، وO(n·q) إجمالًا.

ماذا لو أمكن أن تتغير المصفوفة بين الاستعلامات؟

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

def sumRange(nums, queries):
    # اكتب الكود هنا

اختبار #1

اختبار #2

الوسائط

nums = [3, -2, 5, 1, -4, 6]
queries = [[0, 2], [1, 4], [3, 3]]

الإخراج المتوقع

[6, 0, 1]