백준 1725(히스토그램)세그먼트 트리

세그먼트 트리란 잘게 나누어서 많은 요청에 대해서 일처리를 빠르게 해주는 자료구조이다. 

 

만약에 2 3 4 6 8 1 수열에 대해서 i ~ j번째까지의 합을 구하고 싶다고 한다면 O(n)의 시간이 소요될 것이다. 하지만 여기서  m번 x번째 수열의 값을 바꾸고 다시 계산을 한다고 하면 O(nm)의 시간이 소요된다. 

 

보다 빠르게 계산을 하기 위해서 자료들을 구간별로 나누어서 저장한 뒤에 필요한 수들의 호출 횟수를 줄여서 계산을 진행한다. 

 

세그먼트 트리는 완벽 이진트리로 구성되어서 어떤 수의 변경, 합은 O(log n)의 시간만큼 소요된다. 

만약에 n,m의 값들이 커진다면 시간차이는 기하급수적으로 늘어날 것이다. 

 

그래서 쿼리가 많을 때에는 세그먼트 트리를 사용한다. 

 

세그먼트 트리는 세 단계로 나뉜다.

 

주어진 처음 데이터로 세그먼트 트리를 구현한다. 

쿼리 함수를 구현한다.

결과값 호출 함수를 구현한다.

 

여기서 세그먼트 트리를 구현하는 방법은

top - down

bottom - up 두 개로 나뉘는데 

 

이 문제에서는 n이 2의 거듭 제곱꼴이 아니므로 top - down의 재귀적 성질을 이용한다. 

노드의 index 좌측 자식은 2*index, 우측은 2*index +1 인 성질을 이용해서 세그먼트 트리를 구성한다. 

 

재귀함수의 성질로 먼저 leaf 노드에 도달후에 leaf 노드들의 최소, 최대, 합, 차 꼴로 상위 노드들의 값을 결정해서 세그먼트 트리를 구현한다. 

 

쿼리 함수는 원하는 구간에서 원하는 노드의 값을 변경, 호출 한다. 

 

이 문제에서는 노드값에 구간의 최소값 인덱스를 저장한다. 

 

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

typedef long long ll;

int n;
vector<int> arr;
vector<int> tree;

void init(int node, int start, int end) {
	if (start == end) {
		tree[node] = start;
		return;
	}
	else {
		int mid = (start + end) / 2;
		init(node * 2, start, mid);
		init(node * 2 + 1, mid + 1, end);

		if (arr[tree[node * 2]] <= arr[tree[node * 2 + 1]]) 
			tree[node] = tree[node * 2];
		
		else 
			tree[node] = tree[node * 2 + 1];
	}
}

int query(int node, int start, int end, int left, int right){
	if (left > end || right < start) 
		return -1;

	if (end <= right && start >= left) 
		return tree[node];

	int mid = (start + end) / 2;
	int m1 = query(node * 2, start, mid, left, right);
	int m2 = query(node * 2 + 1, mid + 1, end, left, right);
	
	if (m1 == -1) 
		return m2;

	else if (m2 == -1)
		return m1;
	
	else {
		if (arr[m1] <= arr[m2]) 
			return m1;
		
		else 
			return m2;
		
	}
}

ll getMAX(int left, int right) {
	int m = query(1, 0, n-1, left, right);

	ll area = (ll)(right - left + 1)*(ll)arr[m];


	if (m + 1 <= right) {
		ll tmp = getMAX(m + 1, right);

		if (area < tmp) area = tmp;
	}
	if (m - 1 >= left) {
		ll tmp = getMAX(left, m - 1);

		if (area < tmp) area = tmp;
	}
	return area;
}


int main() {
	cin >> n;
	arr.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int h = (int)ceil(log2(n));
	int tree_size = (1 << (h + 1));

	tree.resize(tree_size);

	init(1, 0, n - 1);
	cout << getMAX(0, n - 1) << "\n";
}