صفيف الفرق | استعلام تحديث النطاق في O (1)


مستوى الصعوبة الثابت
كثيرا ما يطلب في Arcesium CodeNation Directi اكسبيديا جوجل كوالكوم
مجموعة مشكلة الاستعلام

يتم منحك ملف عدد صحيح مجموعة ونوعان من الاستعلامات ، أحدهما لإضافة رقم معين في نطاق والآخر لطباعة المصفوفة بأكملها. مشكلة "مصفوفة الفروق | يتطلب استعلام تحديث النطاق في O (1) "منا إجراء تحديثات النطاق في O (1).

مثال

arr[] = {20, 30, 25, 50}

Update(0, 1, 10)

print()

update(0, 2, 20)

update(2, 3, 30)

print()
(30 40 25 50) (50 60 75 80)

تفسير

ستتم إضافة 10 إلى 20 و 30 ، لذلك ستصبح المصفوفة {30 ، 40 ، 25 ، 50}

ثم سنطبع المصفوفة بأكملها.

ستتم إضافة 20 إلى 30 و 40 و 25 ، لذلك ستصبح المصفوفة {50 ، 60 ، 45 ، 50}

ستتم إضافة 10 إلى 45 و 50 ، لذلك ستصبح المصفوفة {50 ، 60 ، 75 ، 80}

ثم مرة أخرى سنطبع المصفوفة بأكملها.

ستتم طباعة مجموعتي القيم بعد إجراء الاستعلامات.

صفيف الفرق | استعلام تحديث النطاق في O (1)

 

خوارزمية لصفيف الفرق

  1. قم بإنشاء مصفوفة بنفس حجم المصفوفة المحددة.
  2. قم بتهيئة الفهرس الأول كعنصر أول مصفوفة ، وآخر فهرس بـ 0. وجميع المؤشرات الأخرى تمتلئ باختلاف العنصر الحالي والعنصر السابق.
  3. لكل استعلام تحديث ، أضف القيمة X إلى الفهرس الأيسر المحدد للصفيف الذي تم إنشاؤه واطرح X من الفهرس الأيمن للصفيف الذي تم إنشاؤه.
  4. لكل استعلام طباعة ، نملأ أولاً مصفوفة الإدخال باستخدام الصيغة A [i] = D [i] + A [i-1]. ثم اطبع القيم.

تفسير

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

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

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

رمز

التنفيذ في C ++ لصفيف الفروق

#include<iostream>

using namespace std;

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

static void update(int dummyArray[], int l, int r, int x)
{
    dummyArray[l] += x;
    dummyArray[r + 1] -= x;
}

void printArray(int arr[], int dummyArray[], int n)
{
    for (int i = 0; i <n; i++)
    {

        if (i == 0)
            arr[i] = dummyArray[i];
        else
            arr[i] = dummyArray[i] + arr[i - 1];

        cout<<arr[i] << " ";
    }

    cout<<endl;
}

int main()
{
    int arr[] = {20,30,25,50};
    int n = sizeof(arr)/sizeof(arr[0]);

    int dummyArray[n + 1];
    buildArray(arr, dummyArray, n);

    update(dummyArray, 0, 1, 10);
    printArray(arr, dummyArray, n);
    update(dummyArray, 0, 2, 20);
    update(dummyArray, 2, 3, 30);

    printArray(arr, dummyArray,n);
    return 0;
}
30 40 25 50
50 60 75 80

التنفيذ في Java for Difference Array

class differenceArray
{
    static void buildArray(int arr[], int dummyArray[])
    {

        int n = arr.length;

        dummyArray[0] = arr[0];
        dummyArray[n] = 0;
        for (int i = 1; i < n; i++)
            dummyArray[i] = arr[i] - arr[i - 1];
    }
    
    static void update(int dummyArray[], int left, int right, int x)
    {
        dummyArray[left] += x;
        dummyArray[right + 1] -= x;
    }
    
    static int printArray(int arr[], int dummyArray[])
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (i == 0)
                arr[i] = dummyArray[i];
            else
                arr[i] = dummyArray[i] + arr[i - 1];

            System.out.print(arr[i] + " ");
        }

        System.out.println();

        return 0;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {20, 30, 25, 50};
        int n = arr.length;
        int dummyArray[] = new int[n + 1];

        buildArray(arr, dummyArray);

        update(dummyArray, 0, 1, 10);
        printArray(arr, dummyArray);
        update(dummyArray, 0, 2, 20);
        update(dummyArray, 2, 3, 30);

        printArray(arr, dummyArray);
    }
}
30 40 25 50
50 60 75 80

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

تعقيد الوقت

يا (ف) أين "Q" هو عدد استعلامات الطباعة التي يتم تنفيذها أثناء استعلام التحديث يا (1) مرة.

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في المصفوفة. منذ أن أنشأنا مصفوفة فرق إضافية ، لدينا تعقيد فضاء خطي.