সমস্যা বিবরণ
n সংখ্যক ইন্টিজারের একটি অ্যারে এবং q সংখ্যক কোয়েরি দেওয়া আছে, প্রতিটি কোয়েরিতে l থেকে r পর্যন্ত একটি রেঞ্জ থাকে। l – r রেঞ্জের জন্য সর্বোচ্চ প্রিফিক্স-সাম বের করতে হবে।
উদাহরণ
ইনপুট অ্যারে arr[] = {-1, 2, 3, -5} এবং কোয়েরি = 2 এবং রেঞ্জগুলো: l = 0, r = 3 l = 1, r = 3 তবে আউটপুট হবে 4 এবং 5।
- ১ম কোয়েরির রেঞ্জ (0, 3) এ [-1, 2, 3, -5] আছে, যেহেতু এটি প্রিফিক্স, তাই আমাদের -1 থেকে শুরু করতে হবে। অতএব, সর্বোচ্চ প্রিফিক্স সাম হবে -1 + 2 + 3 = 4
- ২য় কোয়েরির রেঞ্জ (1, 3) এ [2, 3, -5] আছে, যেহেতু এটি প্রিফিক্স, তাই আমাদের 2 থেকে শুরু করতে হবে। অতএব, সর্বোচ্চ প্রিফিক্স সাম হবে 2 + 3 = 5
এল्गরিদম
- একটি সেগমেন্ট ট্রি বিল্ড করুন যেখানে প্রতিটি নোড দুটি মান সংরক্ষণ করবে: sum এবং prefix_sum, এবং এর ওপর রেঞ্জ কোয়েরি করুন সর্বোচ্চ প্রিফিক্স সাম বের করার জন্য।
- সর্বোচ্চ প্রিফিক্স সাম বের করার জন্য দুটি জিনিস প্রয়োজন: একটি হলো যোগফল এবং অন্যটি প্রিফিক্স সাম।
- মার্জিং দুটি জিনিস রিটার্ন করবে: রেঞ্জগুলোর যোগফল এবং প্রিফিক্স সাম যেটি সংরক্ষণ করবে max(prefix.left, prefix.sum + prefix.right) সেগমেন্ট ট্রিতে।
- যেকোনো দুটি রেঞ্জ কম্বাইন করার জন্য সর্বোচ্চ প্রিফিক্স সাম হয় বাম পক্ষের প্রিফিক্স সাম হবে অথবা বাম পক্ষের যোগফল + ডান পক্ষের প্রিফিক্স সাম, যেটি সর্বোচ্চ সেটি বিবেচনা করা হবে।
উদাহরণ
#include <bits/stdc++.h> using namespace std; typedef struct node { int sum; int prefix; } node; node tree[4 * 10000]; void build(int *arr, int idx, int start, int end) { if (start == end) { tree[idx].sum = arr[start]; tree[idx].prefix = arr[start]; } else { int mid = (start + end) / 2; build(arr, 2 * idx + 1, start, mid); build(arr, 2 * idx + 2, mid + 1, end); tree[idx].sum = tree[2 * idx + 1].sum + tree[2 * idx + 2].sum; tree[idx].prefix = max(tree[2 * idx + 1].prefix, tree[2 * idx + 1].sum + tree[2 * idx + 2].prefix); } } node query(int idx, int start, int end, int l, int r) { node result; result.sum = result.prefix = -1; if (start > r || end < l) { return result; } if (start >= l && end <= r) { return tree[idx]; } int mid = (start + end) / 2; if (l > mid) { return query(2 * idx + 2, mid + 1, end, l, r); } if (r <= mid) { return query(2 * idx + 1, start, mid, l, r); } node left = query(2 * idx + 1, start, mid, l, r); node right = query(2 * idx + 2, mid + 1, end, l, r); result.sum = left.sum + right.sum; result.prefix = max(left.prefix, left.sum + right.prefix); return result; } int main() { int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof(arr) / sizeof(arr[0]); build(arr, 0, 0, n - 1); cout << "Result = " << query(0, 0, n - 1, 3, 5).prefix << endl; return 0; }
আউটপুট
যখন আপনি উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিচের আউটপুট জেনারেট করবে −
Result = -1
