C ++中给定范围的最大前缀和
问题陈述
给定n个整数数组和q个查询，每个查询的范围从l到r。找到范围l–r的最大前缀和。
示例
If input array is arr[] = {-1, 2, 3, -5} and
queries = 2 and ranges are:
l = 0, r = 3
l = 1, r = 3 then output will be 4 and 5.第一个查询中的范围(0,3)具有[-1，2，3，-5]，因为它是前缀，所以我们必须从-1开始。因此，最大前缀和为-1+2+3=4
第二个查询中的范围(1,3)具有[2，3，-5]，因为它是前缀，所以我们必须从2开始。因此，最大前缀总和将为2+3=5
算法
建立一个分段树，每个节点存储两个值s（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