문제 개요
n개의 정수로 이루어진 배열과 q개의 쿼리가 주어집니다. 각 쿼리는 l부터 r까지의 범위를 가지며, 해당 범위 내에서 최대 접두사 합(maximum prefix sum)을 찾는 것이 목표입니다.
예시
입력 배열이 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)을 저장하는 세그먼트 트리(segment tree)를 구축하고, 이를 대상으로 범위 쿼리를 수행하여 최대 접두사 합을 구합니다.
- 최대 접두사 합을 구하려면 두 가지 정보가 필요합니다. 하나는 구간의 전체 합(sum), 다른 하나는 접두사 합(prefix sum)입니다.
- 병합(merge) 과정에서는 두 가지 값을 반환합니다. 바로 구간들의 합과, max(prefix.left, prefix.sum + prefix.right)를 저장한 접두사 합입니다.
- 두 구간을 결합할 때의 최대 접두사 합은 왼쪽 구간의 접두사 합이거나, '왼쪽 구간의 전체 합 + 오른쪽 구간의 접두사 합' 중 더 큰 값을 취하게 됩니다.
C++ 구현 예제
#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