Prefix sum ইমপ্লিমেন্টেশন

মুলত আমাদের প্রধান উদ্দেশ্য হলো মেইন এরে থেকে Prefix Sum এর এরে টি তৈরি করা। এবং আগের Range sum Query er প্রবলেমটি সল্ভ করবো।

Code of Range Sum Query using Prefix Sum Technique :

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

int main()
{

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

    vector<long long int> V(N);

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

    
    vector<long long int> prefix_sum(N) ;

    prefix_sum[0] = V[0] ; // প্রিফিক্স সাম এরে এর প্রথম ভ্যালুটি হবে এরে এর প্রথম ভ্যালুটি
 
    for(int i =1 ;i<N ;i++){
        prefix_sum[i] = prefix_sum[i-1]+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

        long long int SUM = 0;

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

        //     SUM += V[j];
        // } // এই লুপটি বাদ দিয়ে এখন আমরা প্রিফিক্স সাম টেকনিক ব্যবহার করবো 
        
        
        if(L==0){
        SUM = prefix_sum[R];
        } // যদি L এর মান ০ হয় তবে L-1 invalid হয়ে যাবে। সেইক্ষেত্রে শুরু থেকে নিয়ে R পর্যন্ত হবে সাম
        else SUM = prefix_sum[R]-prefix_sum[L-1] ; // O(1) 

        cout << SUM << endl;
    }
}

প্রিফিক্স সাম এরে টি তৈরি করার প্রক্রিয়াঃ

• যেহেতু আমরা জানি , যেখানে প্রিফিক্স সামের প্রতিটি ইন্ডেক্স i এ, অরিজিনাল এরে এর 0 থেকে i পর্যন্ত সকল ইন্ডেক্সের ভ্যালু এর যোগফল স্টোর করা থাকবে তাই prefix_sum[0] = V[0] সেট করে দেয়া হয়েছে কারণ প্রিফিক্স সাম এরে এর ০ তম ইন্ডেক্সে শুধু মাত্র মেইন এরে এর ০ তম ইন্ডেক্স এর ভ্যালু থাকবে ।

• এরপর prefix_sum[1] এ থাকবে V[0] + V[1]। যেহেতু prefix_sum[0] = V[0] তাই আমরা prefix_sum[1] এ prefix_sum[0] + V[1] করলাম

• এরপর prefix_sum[2] এ থাকবে V[0] + V[1] +V[2]. যেহেতু prefix_sum[1] = V[0] +V[1] তাই আমরা prefix_sum[2] এ prefix_sum[1] + V[2] করলাম.

• এইভাবে করে আমরা n-1 পর্যন্ত সব ভ্যালু গুলা O(N) টাইমে বের করে ফেলতে পারবো।

এইবার আমরা Sum (L,R) = Prefix_sum[R] - Prefix_sum[L-1]

এই সুত্রের সাহায্যে প্রতিটি কুয়েরি এর উত্তর O(1) এ দিতে পারবো ।

এখন যদি আমরা পুরো কোড টির টাইম কমপ্লেক্সিটি এনালাইসিস করি তবে দেখতে পারবো , এর টাইম কমপ্লেক্সিটি হলো O(N + Q*1) এবং N , Q <= 10^5 তাই এই কোডের total operations হবে 10^5+10^5 = 2* 10^5 . যা এক সেকেন্ডের মধ্যে খুব সহজে পাস করে ফেলবে। সুতারাং আমরা আমাদের আগের O(Q*N) / O (N^2) কমপ্লেক্সিটি থেকে এখন O(N) এ নিয়ে আসলাম কমপ্লেক্সিটি যা আসলে অনেক বিরাট ইম্প্রুভমেন্ট। এর থেকে বুঝা যায় প্রিফিক্স সাম টেকনিক এর গুরুত্ব আসলে কতটুকু।