বাইনারি ইনডেক্সড ট্রি ব্যবহার করে সর্বোচ্চ যোগফল বাড়মান সাবসিকোয়েন্স (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের n সংখ্যক পূর্ণসংখ্যা সহ একটি অ্যারে arr[] দেওয়া আছে। আমাদের কাজ হল বাইনারি ইনডেক্সড ট্রি ব্যবহার করে সর্বোচ্চ যোগফল বাড়মান সাবসিকোয়েন্স খুঁজে বের করার C++ প্রোগ্রাম তৈরি করা।

অ্যারেতে উপাদান ব্যবহার করে আমাদের সর্বোচ্চ যোগফল облада করা এমন একটি বাড়মান সাবসিকোয়েন্স খুঁজে বের করতে হবে।

বাড়মান সাবসিকোয়েন্স (Increasing Subsequence): এমন একটি সাবসিকোয়েন্স যেখানে বর্তমান উপাদানের মান আগের পজিশনের উপাদানের চেয়ে বড়।

বাইনারি ইনডেক্সড ট্রি (Binary Indexed Tree): এটি একটি ডেটা স্ট্রাকচার যা এক ধরনের ট্রি। আমরা ট্রিতে উপাদান যোগ বা বাদ দিতে পারি কার্যকরভাবে।

arr[] = {5, 1, 7, 3, 8, 2}

20

সাবসিকোয়েন্স: {5, 7, 8} = 5 + 7 + 8 = 20
{1, 3, 8} = 1 + 3 + 8 = 12
{1, 7, 8} = 1 + 7 + 8 = 16

এই সমস্যাতে, আমাদের বাইনারি ইনডেক্স ট্রি ব্যবহার করে সর্বোচ্চ যোগফল বের করতে হবে। এর জন্য, আমরা অ্যারেতে উপাদান থেকে একটি বাইনারি ইনডেক্স ট্রি তৈরি করব ম্যাপ ব্যবহার করে। তারপর অ্যারেতে উপাদানগুলো দিয়ে ইটারেট করে, প্রতিটি উপাদানের জন্য আমাদের বাইনারি ইনডেক্স ট্রিতে মান পর্যন্ত সব উপাদানের যোগফল বের করতে হবে। এবং তারপর সব মানের সর্বোচ্চ যোগফল ফেরত দিতে হবে।

#include 
using namespace std;

int calcMaxSum(int BITree[], int index) {
    int sum = 0;
    while (index > 0) {
        sum = max(sum, BITree[index]);
        index -= index & (-index);
    }
    return sum;
}

void updateTreeVal(int BITree[], int newIndex, int index, int sumVal) {
    while (index <= newIndex) {
        BITree[index] = max(sumVal, BITree[index]);
        index += index & (-index);
    }
}

int calcMaxSumBIT(int arr[], int n) {
    int uniqCount = 0, maxSum;
    map BinaryIndexTree;
    
    for (int i = 0; i < n; i++) {
        BinaryIndexTree[arr[i]] = 0;
    }
    
    for (map::iterator it = BinaryIndexTree.begin(); it != BinaryIndexTree.end(); it++) {
        uniqCount++;
        BinaryIndexTree[it->first] = uniqCount;
    }
    
    int* BITree = new int[uniqCount + 1];
    for (int i = 0; i <= uniqCount; i++) {
        BITree[i] = 0;
    }
    
    for (int i = 0; i < n; i++) {
        maxSum = calcMaxSum(BITree, BinaryIndexTree[arr[i]] - 1);
        updateTreeVal(BITree, uniqCount, BinaryIndexTree[arr[i]], maxSum + arr[i]);
    }
    
    return calcMaxSum(BITree, uniqCount);
}

int main() {
    int arr[] = {5, 1, 7, 3, 8, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum sum increasing subsequence using binary indexed tree is " << calcMaxSumBIT(arr, n);
    return 0;
}

The maximum sum increasing subsequence using binary indexed tree is 20