본문 바로가기

Computer Science/Algorithms & Problem Solving

최대 부분합과 쿼리

최대 부분합 문제를 $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';
	}
}

 

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

'Computer Science > Algorithms & Problem Solving' 카테고리의 다른 글

2021-08-01 Problem Solving  (0) 2021.08.01
Generalized Sorting with Predictions  (0) 2021.05.05
Minimums on the Edges 풀이  (0) 2020.10.19
최대 부분합과 쿼리  (0) 2020.06.06
Patience Sort  (0) 2020.05.24
Kruskal's Algorithm과 MST의 성질  (0) 2020.03.13