समस्या कथन
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 होगा
एल्गोरिदम
- एक सेगमेंट ट्री बनाएं जहां प्रत्येक नोड दो मान s (सम और प्रीफिक्स_सम) संग्रहीत करता है, और इस पर रेंज क्वेरी करें ताकि अधिकतम प्रीफिक्स योग मिल सकें।
- अधिकतम प्रीफिक्स योग ढूंढने के लिए, हमें दो चीजों की आवश्यकता होगी, एक योग और दूसरा प्रीफिक्स योग
- मर्जिंग दो चीजें लौटाएगा, रेंज का योग और प्रीफिक्स योग जो सेगमेंट ट्री में 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
