استعلامات مجموع النطاق بدون تحديثات


مستوى الصعوبة سهل
كثيرا ما يطلب في بلاك روك جنرال إلكتريك للرعاية الصحية مختبرات Moonfrog سينوبسيس تاكسي فور Twilio
مجموعة لارسن وتوبرو مشكلة الاستعلام

المشكلة بيان

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

مثال

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

تفسير

مجموع كل الأرقام بين النطاق (0 ، 4) بشكل شامل هو 40 ومجموع كل الأرقام بين النطاق (1 ، 3) شاملًا هو 24.

استعلامات مجموع النطاق بدون تحديثات

 

خوارزمية

  1. قم بإنشاء مصفوفة sumArray بنفس حجم المصفوفة المحددة.
  2. اجتياز المصفوفة المحددة وتخزين مجموع عنصر sumArray السابق والعنصر الحالي للصفيف المحدد وتخزينه في sumArray.
  3. لكل استعلام ، إذا كان اليسار يساوي 0 ، فقم بإرجاع sumArray [right] ،
  4. عدا ذلك ، يتم إرجاع sumArray [يمين] - sumArray [يسار - 1].

تفسير

لقد قدمنا ​​مصفوفة من الأعداد الصحيحة والنطاق ، وقد طُلب منا معرفة مجموع كل العناصر داخل النطاق المحدد لكل استعلام. يتكون كل من الاستعلامات من نطاق كنقطة بداية ونهاية النطاق. هذا السؤال لا يتضمن أي استفسار تحديث. هذا يعني أنه ليست هناك حاجة لتحديث أي من الأشياء أثناء معرفة إجابة الاستعلام. سنقوم فقط ببناء المصفوفة المحددة بحيث يكون مجموع كل العناصر من 0 فهرس إلى الفهرس الحالي في الموضع i من المصفوفة المبنية. بهذه الطريقة ، سيتم حل كل استعلام في O (1) ، مع مساحة إضافية لـ O (n).

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

عندما نتلقى استعلامًا يتكون من أي نطاق ، وإذا وجدنا أن النقطة اليسرى أو نقطة البداية للنطاق تساوي 0 ، فسنقوم فقط بإرجاع قيمة sumArray [يمين] وهذا ما ناقشناه أعلاه ، هل النطاق الأيسر هو لا يساوي 0 سنعيد الفرق بين sumArray [right] و sumArray [left-1]. ستكون هذه الإجابات المطلوبة. هذا النهج هو أيضًا أحد أسهل الطرق التي نستخدمها البرمجة الديناميكية.

رمز

كود C ++ لاستعلامات مجموع النطاق بدون تحديثات

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

كود جافا لاستعلامات مجموع النطاق بدون تحديثات

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

تحليل التعقيد

تعقيد الوقت

يا (N + Q) ،  لأننا نحتاج إلى O (N) لحساب sumArray ثم وقت O (1) لكل استعلام.

تعقيد الفضاء

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