এই সমস্যায়, আমাদের n পূর্ণসংখ্যাগুলির একটি অ্যারে অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল C++ এ বাইনারি ইনডেক্সড ট্রি ব্যবহার করে সর্বাধিক যোগফল বাড়ানোর অনুগামী খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা − আমাদের অ্যারের উপাদানগুলি ব্যবহার করে সর্বাধিক যোগফলের সাথে একটি ক্রমবর্ধমান অনুক্রম খুঁজে বের করতে হবে৷
পরবর্তী বৃদ্ধি − পরবর্তীতে যেখানে বর্তমান উপাদানটির মান পূর্ববর্তী অবস্থানে থাকা উপাদানটির চেয়ে বেশি৷
বাইনারি ইনডেক্সড ট্রি - এটি একটি ডেটা স্ট্রাকচার যা এক ধরনের গাছ। আমরা কার্যকর উপায়ে গাছ থেকে উপাদান যোগ বা অপসারণ করতে পারি।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {5, 1, 7, 3, 8, 2} আউটপুট
20
ব্যাখ্যা
Subsequences:
{5, 7, 8} = 5 + 7 + 8 = 20
{1, 3, 8} = 1 + 3 + 8 = 12
{1, 7, 8} = 1 + 7 + 8 = 16 সমাধান পদ্ধতি
এই সমস্যায়, আমাদের একটি বাইনারি ইনডেক্স ট্রি ব্যবহার করে সম্ভাব্য সর্বাধিক সামঞ্জস্য খুঁজে বের করতে হবে। এর জন্য, আমরা অ্যারের উপাদান থেকে একটি মানচিত্র ব্যবহার করে একটি বাইনারি ইনডেক্স ট্রি তৈরি করব। তারপরে অ্যারের উপাদানগুলিকে পুনরাবৃত্তি করে, foreach এলিমেন্ট ব্যবহার করে আমাদের বিআইটিতে মান পর্যন্ত সমস্ত উপাদানের যোগফল খুঁজে বের করতে হবে। এবং তারপরে সমস্ত মানের সর্বোচ্চ যোগফল ফেরত দিন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <bits/stdc++.h>
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<int, int> BinaryIndexTree;
for (int i = 0; i < n; i++) {
BinaryIndexTree[arr[i]] = 0;
}
for (map<int, int>::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
