최대 부분합과 쿼리

최대 부분합 문제를 $O(n)$에 푸는 것은 쉬운 일이다. 하지만, 배열을 업데이트 하는 질의가 주어진다면, 이는 쉬운 일이 아니다. 이와 관련한 문제가 근 몇 년간 여러 대회에 출제되었으며, 신기하게도 한국인들 사이에서는 유독 잘 알려져 있는 테크닉이다.

 

이 글에서는 다음 두 가지 쿼리를 $O(n \log n)$ 전처리 후 쿼리당 $O(\log n)$에 처리하는 방법을 제시한다.

• update(i, value) - 배열의 i번째 index의 값을 value로 업데이트한다
• maxsum(left, right) - [left, right] 범위의 최대 부분합을 반환한다

기본적으로, 세그먼트 트리를 응용하여 문제를 해결한다. 세그먼트 트리의 노드를 다음과 같이 정의해주자.

 

struct Node{
    int left, right;
    long long left_max, right_max, cur_max, cur_sum;
};

 

노드가 나타내는 구간이 [left, right]라 할 때, 각 변수에는 다음과 같은 값을 저장한다.

• left_max: [left, right]의 left를 포함하는 부분합 가운데 최대인 것
• right_max: [left, right]의 right를 포함하는 부분합 가운데 최대인 것
• cur_max: [left, right]의 최대 부분합
• cur_sum: [left, right]에 속하는 모든 값의 합

예를 들어, 노드가 나타내는 부분 배열이 -10, 10, 5, 3, -15라 하면, cur_max는 18, left_max는 8, right_max = 3이 된다.

 

이 노드 구조체를 활용하여 세그먼트 트리를 만들기 위해서는 두 자식 노드 $l$, $r$의 값으로 부터 부모 노드 $n$의 값을 업데이트 할 수 있으면 된다. 이는 다음과 같이 할 수 있다.

• $\tt n.left\_max \leftarrow \max(\color{red}{l.left\_max}, \, \color{blue}{l.cur\_sum + r.left\_max})$
• $\tt n.right\_max \leftarrow \max(\color{red}{l.right\_max + r.cur\_sum }, \, \color{blue}{r.right\_max})$
• $\tt n.cur\_max \leftarrow \max(\color{red}{l.cur\_max},\,  \color{purple}{r.cur\_max}, \, \color{blue}{l.right\_max + r.left\_max})$
• $\tt n.cur\_sum \leftarrow \color{red}{l.cur\_sum} + \color{blue}{r.cur\_sum}$

이와 관련한 가장 대표적인 연습 문제는 백준 온라인 저지의 연속합과 쿼리 문제이다. 아래는 나의 C++ 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

const int INF = 1E9;

struct Node{
	int s, m, l, r;
	Node(){ s = 0, m = -INF, l = -INF, r = -INF; }
};

Node merge(Node left, Node right){
	Node p;
	p.s = left.s + right.s;
	p.l = max(left.l, left.s+right.l);
	p.r = max(right.r, left.r+right.s);
	p.m = max(left.r+right.l, max(left.m, right.m));
	return p;
}

struct SegmentTree{
	vector<Node> tree;
	int card;
	SegmentTree(){}
	void init(int Size){
		tree.clear();
		int p = 1;
		while (p < Size) p *= 2;
		tree.resize(p*2);
		card = p;
	}
	void update(int i, int v){
		int node = (tree.size() >> 1) + i;
		tree[node].s += v;
		tree[node].m = tree[node].s;
		tree[node].l = tree[node].m;
		tree[node].r = tree[node].m;
		node = node >> 1;
		while (node){
			int left = 2 * node;
			int right = 2 * node + 1;
			tree[node].s += v;
			tree[node].l = max(tree[left].l, tree[left].s + tree[right].l);
			tree[node].r = max(tree[right].r, tree[right].s + tree[left].r);
			tree[node].m = max(tree[left].r + tree[right].l, max(tree[left].m, tree[right].m));
			node = node >> 1;
		}
	}
	Node query_node(int node, int begin, int end, int left, int right){
		if (right < begin || end < left){
			Node null_node;
			return null_node;
		}
		if (left <= begin && end <= right) return tree[node];
		int mid = (begin + end) >> 1;
		Node l = query_node(2*node, begin, mid, left, right);
		Node r = query_node(2*node+1, mid+1, end, left, right);
		return merge(l, r);
	}

	int query(int node, int begin, int end, int left, int right){
		return query_node(node, begin, end, left, right).m;
	}
} seg;

int N, Q;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> N;
	seg.init(N);
	for (int i=1; i<=N; i++){
		int t;
		cin >> t;
		seg.update(i-1, t);
	}
	cin >> Q;
	while (Q--){
		int a, b;
		cin >> a >> b;
		cout << seg.query(1, 0, seg.card-1, a-1, b-1) << '\n';
	}
}

 

아래는 이를 응용하여 해결할 수 있는 문제의 목록이다. 추후 더 알게되면 업데이트 할 예정이다.

• 금광 (KOI 2014 중등부 4번)
• Ice Skates (POI 2008/2009 Stage 2 4번)
• 구간 합 최대? 2 (제1회 웰노운컵 A2번)
• Strike Zone (ICPC Asia Regional - Seoul 2019 H번)
• 내 생각에 A번이었던 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) (Good Bye, BOJ 2019! E번)
• SPOJ GSS1
• SPOJ GSS3