পার্থক্য অ্যারে | ও (1) এ ব্যাপ্তি আপডেটের ক্যোয়ারী


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় আরেসিয়াম কোডনেশন ডাইরেক্টি এক্সপিডিয়া গুগল কোয়ালকম
বিন্যাস প্রশ্ন সমস্যা

আপনি একটি দেওয়া হয় পূর্ণসংখ্যা বিন্যাস এবং দুটি ধরণের ক্যোয়ারী, একটি হ'ল একটি পরিসরে একটি প্রদত্ত সংখ্যা যুক্ত করা এবং অন্যটি পুরো অ্যারে প্রিন্ট করা। সমস্যা "পার্থক্য অ্যারে | ও (1) "এ রেঞ্জ আপডেট ক্যোয়ারীটি আমাদের ও (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 become হয়ে যাবে

তারপরে আমরা পুরো অ্যারে প্রিন্ট করব।

20 30, 40 এবং 25 এ যোগ করা হবে, সুতরাং অ্যারে হয়ে যাবে 50 ডলার, 60, 45, 50}

10 টি 45 এবং 50 এ যুক্ত করা হবে, সুতরাং অ্যারেটি 50 ডলার, 60, 75, 80 become হয়ে যাবে

তারপরে আবার আমরা পুরো অ্যারে প্রিন্ট করব।

মান দুটি সেট প্রশ্নের সম্পাদন শেষে মুদ্রিত করা হবে।

পার্থক্য অ্যারে | ও (1) এ ব্যাপ্তি আপডেটের ক্যোয়ারী

 

পার্থক্য অ্যারের জন্য অ্যালগরিদম

  1. প্রদত্ত অ্যারে হিসাবে একই আকারের একটি অ্যারে তৈরি করুন।
  2. প্রদত্ত অ্যারের প্রথম উপাদান হিসাবে প্রথম সূচকটি আরম্ভ করুন এবং সর্বশেষ সূচকটি 0 দিয়ে দিন এবং অন্যান্য সমস্ত সূচকগুলি বর্তমান এবং পূর্ববর্তী উপাদানগুলির পার্থক্যে পূর্ণ filled
  3. প্রতিটি আপডেটের ক্যোয়ারির জন্য, তৈরি অ্যারের প্রদত্ত বাম সূচিতে মান মান যুক্ত করুন এবং তৈরি অ্যারের ডান সূচক থেকে এক্স বিয়োগ করুন।
  4. প্রতিটি মুদ্রণ ক্যোয়ারির জন্য, প্রথমে আমরা ইনপুট অ্যারে পূরণ করি A [i] = D [i] + A [i-1] সূত্রটি ব্যবহার করে। তারপরে মানগুলি মুদ্রণ করুন।

ব্যাখ্যা

একটি অ্যারে এবং একটি সংখ্যা এবং দুটি ধরণের ক্যোয়ারী দেওয়া হয়েছে। সুতরাং আমাদের জিজ্ঞাসা দুটি ধরণের করতে হবে। সংখ্যার এক্স এর সাথে আমাদের দুটি সংখ্যার রেঞ্জের প্রতিনিধিত্ব করবে So সুতরাং, আমাদের কাজ হল প্রদত্ত ব্যাপ্তির মধ্যবর্তী সমস্ত সূচকে X নম্বর যুক্ত করা। পদ্ধতিগুলির মধ্যে একটি হ'ল নিষ্পাপ দৃষ্টিভঙ্গি ব্যবহার করা যেতে পারে। তার জন্য, যখনই আমাদের মানগুলি আপডেট করার প্রয়োজন হয় তখন প্রতিবার প্রদত্ত অ্যারেটি অতিক্রম করুন।

এখানে একটি আরও ভাল সমাধান আলোচনা করা হয়েছে, যা পার্থক্য রাখে এমন একটি অতিরিক্ত অ্যারে তৈরি করা। এ কারণেই এটিকে একটি পার্থক্য অ্যারে বলা হচ্ছে। প্রথমে পার্থক্য অ্যারের প্রথম উপাদানটি ইনপুট অ্যারের প্রথম উপাদান হিসাবে সূচনা করুন। তারপরে পার্থক্য অ্যারের শেষ উপাদানটি 0 এ নির্ধারণ করুন এর পরে, আমরা অ্যারের মধ্য দিয়ে চলে যাব এবং বর্তমান সূচকগুলিতে পার্থক্য অ্যারে বর্তমান মান এবং পূর্ববর্তী মানের পার্থক্য সংরক্ষণ করব।

আমরা একটি আপডেট কোয়েরি পেলে আমরা একটি পরিসীমা হিসাবে মানগুলি পাব। পাশাপাশি আমাদের একটি নম্বর সরবরাহ করা হয়। তারপরে আমরা সেই সংখ্যাটি যুক্ত করতে চলেছি রেঞ্জের পার্থক্য অ্যারেতে বাম সূচকে। একইভাবে পার্থক্য অ্যারের ডান সূচক থেকে মান এক্সটি বিয়োগ করুন। অ্যারে প্রিন্ট করার জন্য আমরা অ্যারের মধ্য দিয়ে অতিক্রম করব এবং শূন্য সূচক মানের জন্য আমরা প্রদত্ত অ্যারের মানটি তৈরি করেছি হিসাবে তৈরি করব, অন্যথায় আমরা তৈরি অ্যারের যোগফল এবং প্রদত্ত অ্যারের পূর্ববর্তী মান পাব এবং নির্দিষ্ট সূচকের জন্য সেই মানটি মুদ্রণ করুন।

কোড

পার্থক্য অ্যারের জন্য সি ++ তে বাস্তবায়ন

#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

পার্থক্য অ্যারের জন্য জাভাতে বাস্তবায়ন

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) সময়।

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। যেহেতু আমরা একটি অতিরিক্ত পার্থক্য অ্যারে তৈরি করেছি, আমাদের লিনিয়ার স্পেস জটিলতা রয়েছে।