Range Sum Query (Codeforces)

Problem Link : https://codeforces.com/group/MWSDmqGsZm/contest/219774/problem/Y

Question Analysis : প্রবলেমে বলা হয়েছে আপনাকে দুইটি নাম্বার N এবং Q দেয়া হবে। একটি N সাইজের এরে দেয়া হবে। এরপর থেকে Q সংখ্যক কুয়েরি জিজ্ঞেস করা হবে যেখানে প্রত্যেকটি কুয়েরি তে দুটি ভ্যালু দেয়া থাকবে L এবং R. আপনার প্রত্যেকটি কুয়েরি এর জন্য উত্তর দিতে হবে , উক্ত এরেটি্র L নম্বর পজিশন থেকে R নম্বর পজিশন পর্যন্ত যে ভ্যালু গুলা আছে তাদের যোগফল কতো। Example Analysis : আমরা দ্বিতীয় Example টি নিয়ে আলোচনা করবো।

Array	5	5	2	3
Position	1	2	3	4

এখানে কুয়েরি গুলা হলোঃ প্রথম কুয়েরি -> 1 3 অর্থাৎ L এর মান হলো ১ এবং R এর মান হলো ৩। অর্থাৎ আমাদের ১ নাম্বার পজিশন থেকে ৩ নাম্বার পজিশন পর্যন্ত যে ভ্যালু গুলা আছে তার যোগ ফল দেখাতে হবে । যোগ ফল হলো = ৫+৫+২ = ১২। তাই 1 3 এর জন্য উত্তর এসেছে 12.

দ্বিতীয় কুয়েরি -> 2 3 অর্থাৎ L এর মান হলো ২ এবং R এর মান হলো ৩। অর্থাৎ আমাদের ২ নাম্বার পজিশন থেকে ৩ নাম্বার পজিশন পর্যন্ত যে ভ্যালু গুলা আছে তার যোগ ফল দেখাতে হবে । যোগ ফল হলো = ৫+২ = ৭। তাই 2 3 এর জন্য উত্তর এসেছে 7.

তৃতীয় কুয়েরি -> 1 4 অর্থাৎ L এর মান হলো ১ এবং R এর মান হলো ৪ । অর্থাৎ আমাদের ২ নাম্বার পজিশন থেকে ৩ নাম্বার পজিশন পর্যন্ত যে ভ্যালু গুলা আছে তার যোগ ফল দেখাতে হবে । যোগ ফল হলো = ৫+২ = ৭। তাই 2 3 এর জন্য উত্তর এসেছে 7.

আসেন আমরা প্রবলেমটির সহজ সরল একটি সলিউশন লেখার চেষ্টা করি। Naive Approach :

#include <bits/stdc++.h>
using namespace std;

int main()
{

    int N, Q;
    cin >> N >> Q;

    vector<int> V(N);

    for (int i = 0; i < N; i++) // O(N) 
    {
        cin >> V[i];
    }

    for (int i = 1; i <= Q; i++) // O(Q) 
    {

        int L, R;
        cin >> L >> R;
        L--;   R--; // converting the position to array index

        int SUM = 0;

        for (int j = L; j <= R; j++) // O(N) -> কারণ আমাদের প্রত্যেকবার L এর মান ১ এবং R এর মান N পর্যন্ত দেয়া হতে পারে  
        {

            SUM += V[j];
        }

        cout << SUM << endl;
    }
}

Code Explanation : উক্ত কোডে আমরা ১৭ নাম্বার লাইন থেকে আমাদের মেইন কুয়েরির পার্ট টুকু করেছি । এখানে আমরা দুটি নাম্বার L এবং R এর ভ্যালু ইনপুটে নিচ্ছি যা মুলত আমাদের রেঞ্জ। এরপর আরেকটি লুপ চালাচ্ছি এই রেঞ্জের জন্য from L to R এবং এই রেঞ্জের মধ্যে যে এরে এলিমেন্ট গুলা আছে তা যোগ করছি। এবং সবশেষে এই যোগফলটি প্রিন্ট করে দিচ্ছি এই কোডের টাইম কমপ্লেক্সিটি হলো O (Q*N). এখন প্রবলেমে আমাদের N এর মান এবং Q এর মান 10^5 পর্যন্ত দেয়া থাকতে পারে . যেহেতু আমাদের কোডের টাইম কমপ্লেক্সিটি O(Q*N) , তাই এই ইনপুটের জন্য আমাদের কোডে Total (10^5 * 10^5) = 10^10 টি অপারেশন চলবে। যেহেতু কম্পিউটার এক সেকেন্ডে 10^8 টি অপারেশন করতে পারে, তাই এই এপ্রোচে এই প্রবলেমটি সল্ভ করা যাবে না। এবং সাবমিট করলে এই প্রবলেমটি TLE দেখাবে। আমরা সামনে একটি টেকনিক শিখবো যার মাধ্যমে এই প্রবলেমটি খুব সহজে এই টাইম লিমিটের মধ্যে করতে পারবো।