[C++] 백준 1725번: 히스토그램 - Segment Tree

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

---

세그먼트 트리 응용 문제

세그먼트 트리를 이용해 구간 합을 미리 구하거나 최솟값을 적는 등으로 활용이 가능했으나,

해당 문제에서는 tree[node]에 가장 작은 값의 인덱스를 집어 넣어 문제를 해결할 수 있다.

 

원리는 아래와 같다.

예제로 살펴보면,

먼저 가장 작은 값의 인덱스인 1을 기준으로 히스토그램의 넓이를 구한다.

이후 1의 왼쪽과 오른쪽을 다시 기준으로 삼아 넓이를 구해 나간다.

 

이 경우 왼쪽은 인덱스가 0인 부분 하나이므로 해당 넓이를 구하고 종료를 하지만,

오른쪽의 경우 해당 부분의 넓이를 구한 후 다시 가장 작은 값의 인덱스를 찾아 위와 같은 방식으로 분할한다.

 

가장 작은 인덱스가 4이므로 4의 넓이를 구하고,

4를 기준 왼쪽과 오른쪽 각각의 넓이를 구한 후 다시 나누어 계산하면 된다.

 

왼쪽의 경우 초록색으로, 오른쪽의 경우 검정색으로 분할하였고,

다시 분할이 되지 않으므로 최종적으로 구했던 넓이 중 가장 큰 값을 반환하면 된다.

 

이를 세그먼트 트리로 구현하였는데,

먼저 각각의 노드에는 l ~ r 번 인덱스까지의 값 중 가장 작은 값의 인덱스를 저장하였다.

int init(int node, int s, int e){
    if(s==e) return tree[node]=s;
    int m=(s+e)/2;
    int l=init(node*2, s, m);
    int r=init(node*2+1, m+1, e);
    return tree[node]=dp[l]<dp[r] ? l : r;
}

 

인덱스를 저장하므로 해당 인덱스를 기준으로 좌 우를 계산할 수 있다.

 

int query(int node, int s, int e, int l, int r){
    if(l>e || r<s) return -1;
    if(s>=l && e<=r) return tree[node];
    int m=(s+e)/2;
    int r1=query(node*2, s, m, l, r);
    int r2=query(node*2+1, m+1, e, l, r);
    if(r1==-1) return r2;
    else if(r2==-1) return r1;
    else return dp[r1]<dp[r2] ? r1 : r2;
}
void solve(int l, int r){
    if(r<l) return;
    int idx=query(1, 1, n, l, r);
    ans=max(ans, dp[idx]*(r-l+1));
    solve(l, idx-1);
    solve(idx+1, r);
}

 

이후에는 넓이를 계산하기 위해 1 ~ N 번까지의 구간을 쪼개주는 solve 함수와,

쪼갠 부분의 가장 작은 값을 가지고 있는 인덱스 번호를 구하기 위한 query 함수를 구현하였다.

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n, ans, dp[100001], tree[1000001];
int init(int node, int s, int e){
    if(s==e) return tree[node]=s;
    int m=(s+e)/2;
    int l=init(node*2, s, m);
    int r=init(node*2+1, m+1, e);
    return tree[node]=dp[l]<dp[r] ? l : r;
}
int query(int node, int s, int e, int l, int r){
    if(l>e || r<s) return -1;
    if(s>=l && e<=r) return tree[node];
    int m=(s+e)/2;
    int r1=query(node*2, s, m, l, r);
    int r2=query(node*2+1, m+1, e, l, r);
    if(r1==-1) return r2;
    else if(r2==-1) return r1;
    else return dp[r1]<dp[r2] ? r1 : r2;
}
void solve(int l, int r){
    if(r<l) return;
    int idx=query(1, 1, n, l, r);
    ans=max(ans, dp[idx]*(r-l+1));
    solve(l, idx-1);
    solve(idx+1, r);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> dp[i];
    init(1, 1, n);
    solve(1, n);
    cout << ans;
}