Prefix Sum and Binary Search

Prefix Sum কী?

Prefix Sum হলো একটি টেকনিক, যার মাধ্যমে অ্যারের নির্দিষ্ট একটা অংশের যোগফল খুব দ্রুত বের করা যায় ।

কেন Prefix Sum ব্যবহার করবো?

আমরা যদি প্রতিবার লুপ চালিয়ে অ্যারের নির্দিষ্ট একটা অংশের যোগফল বের করি, তাহলে তার টাইম কমপ্লেক্সিটি হয় O(n) । কিন্তু Prefix Sum ব্যবহার করলে, একবার আগেই সব হিসাব করে রাখলে, পরে যেকোনো রেঞ্জের যোগফল বের করা যায় O(1) সময়ে।

সাধারণভাবে কীভাবে যোগফল বের করি?

ধরি আমাদের একটি অ্যারে আছে এরকম

int arr[] = {1, 2, 3, 4, 5};

আমরা যদি index 1 থেকে 3 পর্যন্ত যোগফল চাই:

int sum = 0;
for (int i = 1; i <= 3; i++) {
    sum += arr[i];
}

এক্ষেত্রে এর টাইম কমপ্লেক্সিটি হবে O(n)

এখন আমরা যদি Prefix Sum ব্যবহার করে করি

Prefix Sum implementation

আমরা একটি নতুন অ্যারে বানাবো, যেটির প্রতিটি এলিমেন্ট মূল অ্যারের এলিমেন্ট গুলোর এক এক করে যোগ করে রাখা হবে । এটিকে বলা হয় prefix[] অ্যারে।

উদাহরণস্বরূপ, যদি আমাদের মূল অ্যারে হয়:

int arr[] = {1, 2, 3, 4, 5};

তাহলে prefix sum অ্যারে বানানো হবে এভাবে:

int n;
int prefix[n];
prefix[0] = arr[0];

for (int i = 1; i < n; i++) {
    prefix[i] = prefix[i - 1] + arr[i]; // prefix[r] পর্যন্ত যোগফল থেকে prefix[l-1] পর্যন্ত বাদ দিচ্ছি
}

এখানে prefix[i] মানে হলো arr[0] থেকে arr[i] পর্যন্ত সবগুলোর যোগফল।

Prefix Array-এর মানগুলো হবে:

• prefix[0] = 1
• prefix[1] = 1 + 2 = 3
• prefix[2] = 1 + 2 + 3 = 6
• prefix[3] = 1 + 2 + 3 + 4 = 10
• prefix[4] = 1 + 2 + 3 + 4 + 5 = 15

এখন কিভাবে যেকোনো সাবঅ্যারের যোগফল বের করবো?

ধরি আমরা index l থেকে r পর্যন্ত যোগফল জানতে চাই। তখন আমাদের ফর্মুলা হবে:

sum = prefix[r] - prefix[l - 1];

কিন্তু যদি l = 0 হয়, তখন prefix[l - 1] থাকবে না, তাই:

if (l == 0) sum = prefix[r];
else sum = prefix[r] - prefix[l - 1];

উদাহরণ:

ধরি, arr[] = {1, 2, 3, 4, 5}
এবং আমরা চাই 1 থেকে 3 পর্যন্ত যোগফল (মানে 2 + 3 + 4 = 9)

int l = 1, r = 3;
int sum = prefix[r] - prefix[l - 1]; // 10 - 1 = 9

Time Complexity বিশ্লেষণ:

• Prefix অ্যারে তৈরি করতে সময় লাগে O(n)
• এরপর যেকোনো রেঞ্জের যোগফল বের করতে সময় লাগে O(1)

বাইনারি সার্চ কী?

বাইনারি সার্চ একটি অ্যালগরিদম যার মাধ্যমে আমরা একটি সর্ট করা অ্যারে থেকে কোনো নির্দিষ্ট উপাদান খুব সহজে বের করে আনতে পারি ।

কেন বাইনারি সার্চ প্রয়োজন?

আমাদের যদি অনেক বড় একটি ডেটাসেট থাকে, তাহলে একে একে সব এলিমেন্ট খুঁজে বের করা অনেক সময়সাপেক্ষ হয়ে যায় এবং এটি লিনিয়ার সার্চ ব্যবহার করলে সময় লাগে O(n)। কিন্তু যদি আমরা এই ক্ষেত্রে বাইনারি সার্চ ব্যবহার করি, তাহলে এর টাইম কমপ্লেক্সিটি কমে দাঁড়ায় O(log n), যা অনেক দ্রুত।

ধরুন, আপনার কাছে মাত্র ১০টি ডেটা/এলিমেন্ট আছে । আপনি হয়তো খুব সহজেই লিনিয়ার সার্চ (O(n)) ব্যবহার করে কাঙ্ক্ষিত রেজাল্ট বের করে ফেললেন। কিন্তু যদি আপনার ডেটাসেটে ১ লাখ বা ১ কোটি বা তারও বেশি উপাদান থাকে, তখন প্রতিটি উপাদান একে একে খুঁজে বের করা অনেক কঠিন এবং সময়সাপেক্ষ হয়ে পড়ে। ঠিক এখানেই বাইনারি সার্চ আমাদেরকে অনেক সুবিধা দেয়। কারণ এটি প্রতিবার ডেটাসেটকে অর্ধেক করে ভাগ করে অপারেশন চালায়, ফলে অনেক দ্রুত রেজাল্ট বের করা যায় ।

যেমন :

যদি আপনার ডেটাসেটে ১০০টি উপাদান থাকে, বাইনারি সার্চে সর্বোচ্চ প্রায় ৭টি ধাপেই মানটি খুঁজে পাওয়া সম্ভব।

১০,০০০ উপাদান থাকলেও বাইনারি সার্চে প্রায় ১৪টি ধাপেই কাঙ্ক্ষিত মানটি পাওয়া সম্ভব।

১ কোটি উপাদান থাকলেও এটি প্রায় ২৪ ধাপের বেশি লাগবে না!

তুলনামূলকভাবে, লিনিয়ার সার্চে এই ক্ষেত্রগুলোতে ১০০, ১০,০০০, কিংবা ১ কোটি ধাপও লাগতে পারে।

প্রতিবার:

1. দুটি পয়েন্টার নিই: আমরা বুঝার সুবিধার জন্য left and right অথবা যেমন low এবং high pointer বলতে পারি
2. মাঝখানের ইনডেক্স বের করি: mid = low + (high - low) / 2
3. যদি v[mid] == target, তাহলে পাওয়া গেছে
4. যদি v[mid] > target, তাহলে বাম দিকে খুঁজে দেখি
5. যদি v[mid] < target, তাহলে ডান দিকে খুঁজে দেখি

এভাবে প্রতিবার রেঞ্জ অর্ধেক হয়ে যায়।

Note: এটি কেবলমাত্র sorted array এ কাজ করে।

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

int main() {
    vector<int> v = {1, 3, 5, 7, 9, 11}; // Sorted vector
    // NOTE: যদি Sort করা না থাকে তাহলে Sort করে নিতে হবে ।
    int target = 7;

    int low = 0, high = v.size() - 1;
    int index = -1; 

    while (low <= high) {
        int mid = (low + high) / 2;

        if (v[mid] == target) {
            index = mid;
            break;
        } else if (v[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    if (index != -1){
         cout << "Element found at index: " << index << endl;
    } else {
         cout << "Element not found." << endl;
    }
        

    return 0;
}