বিরল সারণী ব্যবহার করে ব্যাপ্তির যোগফল ery


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক পাবলিকিস সেপিয়েন্ট Zoho
বিন্যাস

বিচ্ছিন্ন সারণী সমস্যাটি ব্যবহার করে ব্যাপ্তি যোগ কোয়েরিতে আমাদের একটি পরিসীমা ক্যোয়ারী রয়েছে এবং একটি পূর্ণসংখ্যা দেওয়া হয় বিন্যাস। প্রদত্ত টাস্কটি হ'ল পরিসীমাতে আসা সমস্ত পূর্ণসংখ্যার যোগফল বের করা।

উদাহরণ

ইনপুট:

আরআর [] = {1,4,6,8,2,5}

অনুসন্ধান: {(0, 3), (2, 4), (1, 5)

আউটপুট:

19 16 25

ব্যাখ্যা: পূর্ণসংখ্যার যোগফল যা পরিসীমা 0, 3 সহ অন্তর্ভুক্ত হয় 1 + 4 + 6 + 8 হ'ল 19. আবার, 2, 4 সমেত পরিমাপে সংখ্যার যোগফলের যোগফল 6 + 8 + 2 হয় 16. পূর্ণসংখ্যার যোগফল এটি 1, 5 পরিসীমাটিতে আসে 4 + 6 + 8 + 2 + 5 সহ 25।

বিরল সারণী ব্যবহার করে ব্যাপ্তির যোগফল ery

অ্যালগরিদম

  1. 2 ডি ম্যাট্রিক্স ব্যবহার করে একটি স্পারস টেবিল তৈরি করুন।
  2. অ্যারেটি অতিক্রম করুন এবং স্প্রে_ট্যাবলের প্রতিটি সারি অ্যারেতে চিহ্নিত করুন [i]।
  3. নেস্টি করে অ্যারেটি অতিক্রম করুন, এবং পূর্ববর্তী কলামের স্পারস টেবিলের যোগফল হিসাবে এবং স্পার্স_ টেবিল [i + 2] তে স্পার্স_ট্যাটেল মানটি আপডেট করুন J-1 ] [জে -১] এবং স্পারস_টিটেবল [i] [জে] এ সঞ্চয় করুন।
  4. প্রতিটি ক্যোয়ারী সমাধান করার জন্য, আমরা বাম এবং ডান পেতে পারি, আউটপুটটির মান 0 তে নির্ধারণ করি।
  5. 16 থেকে 0 পর্যন্ত অ্যারেটি অতিক্রম করুন এবং বাম +2 কিনা তা পরীক্ষা করুনj -1 হ'ল সমান এর চেয়ে কম, যদি সত্য হয়,
    1. Sparse_table [বাম] [জে] এ আউটপুট মান যুক্ত করুন এবং যোগফল আউটপুটে সংরক্ষণ করুন।
    2. বাম থেকে বাম + 2 এর মান আপডেট করুন
  6. আউটপুট মান ফিরে।

বিচ্ছুর সারণি ব্যবহার করে ব্যাপ্তির যোগফলের ব্যাখ্যা

একটি অ্যারে এবং একটি কোয়েরি দেওয়া হয়েছে। কোয়েরিতে একটি পরিসরের মধ্যে আসা সমস্ত পূর্ণসংখ্যার যোগফল সন্ধান করুন। আমরা স্পার ছক ধারণাটি ব্যবহার করব। আমরা একটি স্পার ছক তৈরি করব। স্পারস টেবিলটি একটি 2 ডি ম্যাট্রিক্স যেখানে আমরা কিছু ক্রিয়াকলাপ সম্পাদন করতে যাচ্ছি এবং একটি স্পার ছকে মানগুলি সঞ্চয় করতে চলেছি।

2 ডি ঘোষণা করুন জরায়ু। আমরা এক লক্ষ সারি এবং সর্বাধিক ১ col টি কলামের সীমা নিয়েছি। আমরা এখানে বিশেষত 16 নম্বর নিয়েছি কারণ এর পরে আমরা একটি সংখ্যা পাব যা 16 পাওয়ার চেয়ে 2 এর চেয়ে বড়, তাই 5 যথেষ্ট। তারপরে একটি বিরল টেবিল তৈরির প্রথম পর্যায়ে পৌঁছে যাবে। অ্যারের মাধ্যমে ট্র্যাভার করার সময় আমরা প্রদত্ত অ্যারে উপাদান হিসাবে বিচ্ছিন্ন টেবিলের মানগুলি চিহ্নিত বা আপডেট করতে যাচ্ছি। তারপরে নেস্টেড আমরা অ্যারেটি অতিক্রম করতে যাচ্ছি, আবার সারি সংখ্যা কে। I, j-16 এ স্পারস টেবিলের যোগফল হিসাবে i, j-1 এবং স্পর্শ ছককে i + 2 এ যোগ করুনJ-1, জে -১। বিরল সারণির জন্য এটি চূড়ান্ত প্রয়োজনীয় আপডেট হবে।

বাম, ডান পরিসীমা হিসাবে প্রদত্ত প্রতিটি প্রশ্নের জন্য আমাদের অ্যারেটি অতিক্রম করতে হবে, তবে তার আগে আউটপুটটির মান 0 এ সেট করা হবে, তবে 16 থেকে 0 পর্যন্ত অ্যারেটি অতিক্রম করুন, যাতে আমরা প্রতিবার 2 এর শর্তে পাওয়ার পেতে পারি 1 <

বাস্তবায়ন

বিচ্ছিন্ন সারণী ব্যবহার করে ব্যাপ্তির যোগফলের জন্য সি ++ প্রোগ্রাম

#include<iostream>

using namespace std;

const int k = 16;

const int N = 1e5;

long long sparse_table[N][k + 1];

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

    for (int j = 1; j <= k; j++)
        for (int i = 0; i <= n - (1 << j); i++)
            sparse_table[i][j] = sparse_table[i][j - 1] +
                                 sparse_table[i + (1 << (j - 1))][j - 1];
}

long long solveQuery(int Left, int Right)
{
    long long output = 0;
    for (int j = k; j >= 0; j--)
    {
        if (Left + (1 << j) - 1 <= Right)
        {
            output = output + sparse_table[Left][j];

            Left += 1 << j;
        }
    }
    return output;
}

int main()
{
    int arr[] = { 1,4,6,8,2,5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    SparseTable(arr, n);

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

    return 0;
}
19
16
25

স্পার সারণি ব্যবহার করে রেঞ্জের যোগফলের জন্য জাভা প্রোগ্রাম

class SumQueryRange
{
    static int k = 16;

    static int N = 100000;

    static long sparse_table[][] = new long[N][k + 1];

    static void SparseTable(int arr[],int n)
    {
        for (int i = 0; i < n; i++)
            sparse_table[i][0] = arr[i];

        for (int j = 1; j <= k; j++)
            for (int i = 0; i <= n - (1 << j); i++)
                sparse_table[i][j] = sparse_table[i][j - 1] + sparse_table[i + (1 << (j - 1))][j - 1];
    }
    
    static long solveQuery(int Left, int Right)
    {
        long sol = 0;
        for (int j = k; j >= 0; j--)
        {
            if (Left + (1 << j) - 1 <= Right)
            {
                sol = sol + sparse_table[Left][j];

                Left += 1 << j;
            }
        }
        return sol;
    }
    
    public static void main(String args[])
    {
        int arr[] = { 1,4,6,8,2,5};
        int n = arr.length;

        SparseTable(arr, n);

        System.out.println(solveQuery(0, 3));
        System.out.println(solveQuery(2, 4));
        System.out.println(solveQuery(1, 5));
    }
}
19
16
25

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন * লগ (এন)) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

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

ও (এন * লগ (এন)) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

উল্লেখ