Range Sum Query
لديك مصفوفة من الأعداد الصحيحة nums لا تتغير، وقائمة من queries. كل استعلام هو زوج [left, right] من الفهارس التي يبدأ ترقيمها من 0، ويطلب حساب nums[left] + nums[left+1] + ... + nums[right]، مع تضمين الطرفين. أعد الإجابات بالترتيب نفسه للاستعلامات.
الدالة
- numsinteger-array
- مصفوفة الأعداد الصحيحة، نفسها لكل استعلام
- queriesinteger-2d-array
- النطاقات المطلوب جمعها، وكلٌّ منها زوج [left, right] حيث left ≤ right
- تُرجعinteger-array
- مجموع كل نطاق، واحد لكل استعلام، بترتيب الاستعلامات
القيود
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ 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]
- الشرح
- مجموع المصفوفة كلها هو
2 + 7 + 1 + 8 = 18، ومجموع آخر قيمتين هو1 + 8 = 9، والفهرس 0 وحده هو2، والفهرسان من 1 إلى 2 مجموعهما7 + 1 = 8.
+14 اختبارات مخفية عند الإرسال
سؤال إضافي
أصبحت الأعداد الآن تشكّل شبكة، ويطلب كل استعلام حساب مجموع مستطيل محدد بزاويتين. كيف يمكنك توسيع المجاميع التراكمية للإجابة عن كل استعلام بعدد ثابت من العمليات؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تغطي العديد من الاستعلامات قيمًا متقاربة جدًا. ما العمل الذي يمكنك إنجازه مرة واحدة قبل قراءة أي استعلام؟
إذا كنت تعرف مجموع أول
iقيمة لكلi، فسيكون مجموع نطاق ما هو الفرق بين مجموعين من تلك المجاميع.أنشئ
prefixباستخدامprefix[0] = 0وprefix[i+1] = prefix[i] + nums[i]. ثم تكون كل استعلامات[left, right]هيprefix[right+1] - prefix[left].
الحل
نطاق واحد هو حلقة تكرار. المشكلة في عدد النطاقات: يمكن لكل استعلام أن يشمل معظم المصفوفة، لذا فإن جمع عناصر كل نطاق على حدة يكرر عمليات الجمع نفسها مرارًا وتكرارًا. اجمع كل شيء مرة واحدة في مجاميع بادئة، وعندها يصبح كل نطاق عملية طرح واحدة.
اجمع كل نطاق
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
أجب عن كل استعلام على حدة: ابدأ بمجموع يساوي 0، وأضف القيم من nums[left] حتى nums[right]، ثم خزّن الناتج. بالنسبة إلى [1, 4] في [3, -2, 5, 1, -4, 6]، يكون الناتج -2 + 5 + 1 + (-4) = 0.
هذه الطريقة صحيحة، وهي أفضل ما يمكنك فعله لاستعلام واحد: عليك قراءة كل قيمة في النطاق مرة واحدة. لكن التكلفة تكمن في التكرار. قد يشمل الاستعلام ما يصل إلى n قيمة، لذا قد تتطلب q من الاستعلامات ما يصل إلى n × q عملية جمع. مع n = 10^4 و1500 استعلام، يغطي كل منها معظم المصفوفة، فهذا يعني نحو 1.3 × 10^7 عملية جمع، وتقريبًا جميعها تكرار لعمل أُنجز لاستعلام سابق.
إلى جانب قائمة الإجابات، تحتفظ بمجموع واحد، لذا فإن المساحة الإضافية هي O(1).
الخوارزمية
- أنشئ قائمة إجابات فارغة.
- لكل استعلام
[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]، نحصل على prefix = [0, 3, 1, 6, 7, 3, 9]. كل عنصر يساوي العنصر الذي يسبقه مضافًا إليه قيمة واحدة، لذا تتطلب المصفوفة بأكملها n عمليات جمع.
النطاق [left, right] هو مجموع كل ما يصل إلى الفهرس right ويشمله، مطروحًا منه مجموع كل ما يسبق الفهرس left. أي prefix[right+1] - prefix[left]. بالنسبة إلى [1, 4]: prefix[5] - prefix[1] = 3 - 3 = 0. وبالنسبة إلى [0, 2]: prefix[3] - prefix[0] = 6 - 0 = 6. وجود 0 في البداية هو ما يجعل النطاق الذي يبدأ عند الفهرس 0 يعمل دون حالة خاصة.
تستغرق عملية إنشاء المصفوفة O(n)، ثم يستغرق كل استعلام عملية طرح واحدة، لذا يكون الزمن الإجمالي O(n + q) والمساحة الإضافية O(n). لا يتجاوز أي مجموع بادئة هنا 10^4 × 10^4 = 10^8، لذا تكفي الأعداد الصحيحة ذات 32 بت.
الخوارزمية
- أنشئ
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بدلًا من القيمة عند الفهرس 3. - إنشاء
prefixبالطول نفسه لـnums، بحيث تتضمنprefix[i]القيمةnums[i]. عندها تحتاج الفترة التي تبدأ عند0إلىprefix[left-1]، وهو خارج الحدود، وفي Python تُقرأ آخر قيمة بصمت. وتزيل قيمة0الإضافية في البداية هذه الحالة الخاصة. - إيقاف القوة الغاشمة عند
i < right. فكلا طرفَي الفترة مشمولان. - نسيان أن Lua وR تبدآن العد من 1. فاستعلام الفهرسة الصفرية
[left, right]يشمل هناك العناصر منnums[left+1]إلىnums[right+1]، وينزاح فرق المجاميع التراكمية بالطريقة نفسها. - استخدام مجموع من 32 بت عندما تكبر القيم أو الأطوال. أكبر مجموع هنا هو
10^8، لكن مع قيم تقارب10^9يفيض المجموع التراكمي بسرعة، وتكون المصفوفة ذات 64 بت هي الخيار الافتراضي الآمن.
أسئلة شائعة4
ما هي مصفوفة المجاميع التراكمية؟
إنها مصفوفة يكون فيها كل عنصر هو مجموع جميع القيم التي تسبق موضعًا ما: 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) إجمالًا.
لماذا تحتوي مصفوفة البادئات على عنصر واحد أكثر من nums؟
يمثّل prefix[0] = 0 الإضافي بداية المصفوفة الفارغة. وبفضله، تستخدم كل نطاقات الفهارس الصيغة نفسها، بما فيها النطاقات التي تبدأ عند الفهرس 0: prefix[right+1] - prefix[0]. ومن دونه، ستحتاج إلى فرع منفصل للحالة left = 0.
ماذا لو كان من الممكن أن تتغير المصفوفة بين الاستعلامات؟
لذلك، فإن مصفوفة المجاميع السابقة ليست الأداة المناسبة، لأن تحديثًا واحدًا يغيّر كل مجموع بعده، ويكلّف O(n) لإصلاحه. تتعامل شجرة Fenwick أو شجرة المقاطع مع كلٍّ من التحديث ومجموع نطاق في O(log n). عندما لا تتغير المصفوفة أبدًا، تكون المجاميع السابقة العادية أسرع وأقصر.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def sumRange(nums, queries):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
المتوقع
[6, 0, 1]