[백준 16993번] [세그먼트 트리 / 분할 정복] 연속합과 쿼리

이 문제를 통해 세그먼트 트리의 활용법을 제대로 이해해야 한다.

 

해당 쿼리의 연속합을 구하는 과정에서 부분 문제들의 partition울 활용할 수 있을 것 같다는 느낌이 직관적으로 매우 강하게 든다.

이 지점에서 Segment Tree 기법을 생각했어야 한다.

 

Segment tree를 처음 init시키는 과정에서 저장한 정보를 활용하여, 주어진 쿼리의 연속합을 도출할 수 있을 것 같은 느낌이 들면 된다.

 

다만, 문제가 연속합을 도출하기 위해서는 분할정복의 느낌으로 오른쪽과 왼쪽 결과값을 활용해서 도출해주어야하는데

이 과정에서 필요한 정보가 왼쪽을 기준으로 진행했을때의 최대 연속합과 오른쪽으로 진행했을 때의 최대 연속합이다.

또한, 추가적으로 이 모두를 고려했을 때의 최대 연속합이 필요하다.

 

요약하자면 다음과 같다.

int mid = (start + end) / 2를 하면

(start, mid)와 (mid + 1, end) 각 쿼리에 대한 정보를 얻게 되는데

front = (start, mid), back = (mid + 1, end)라 하면

이 과정에서 전체 왼쪽을 기준으로 진행했을 때의 연속합은 max(front 기준 왼쪽 최대 연속 합, front 전체 합 + back 기준 왼쪽 최대 연속합)이 된다.

 

이 과정에서 전체 합이 필요하게 된다.

 

즉, 필요한 인자가 왼쪽과 오른쪽으로 진행했을 때의 최대 연속합, 전체 최대 연속합, 해당 쿼리의 전체 원소의 합이다.

구조체정도로 이 4가지의 인자를 관리하는 Tree를 형성한다.

 

Segment-Tree를 처음 init함으로써 i~j까지의 연속합에 대한 정보를 가지고 있는 쿼리를 저장하는 tree를 만들고

이를 통해 문제에서 주어지는 쿼리 구간에 대한 정보를 이끌어내주면 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

struct node_data{
    int left;
    int right;
    int max;
    int sum;
    node_data() : left(-123456789), right(-123456789), max(-123456789), sum(0)
    {}
    node_data(int temp1, int temp2, int temp3, int temp4) : left(temp1), right(temp2), max(temp3), sum(temp4)
    {}
};

node_data tree[400001];
int arr[100001];

node_data init(int start, int end, int node){
    if(start == end){
        return tree[node] = node_data(arr[start], arr[start], arr[start], arr[start]);
    }
    else{
        int mid = (start + end) / 2;
        node_data front = init(start, mid, node * 2);
        node_data back = init(mid + 1, end, node * 2 + 1);
        return tree[node] = node_data(max(front.left, front.sum + back.left), max(front.right + back.sum, back.right), max(max(front.max, back.max), front.right + back.left), front.sum + back.sum);
    }
}

node_data max_query(int start, int end, int left, int right, int node){
    if(right < start || end < left) return node_data(-123456789, -123456789, -123456789, 0);
    if(left <= start && end <= right) return tree[node];
    
    int mid = (start + end) / 2;
    
    node_data front = max_query(start, mid, left, right, node * 2);
    node_data back = max_query(mid + 1, end, left, right, node * 2 + 1);
    return node_data(max(front.left, front.sum + back.left), max(front.right + back.sum, back.right), max(max(front.max, back.max), front.right + back.left), front.sum + back.sum);
}

int main(void){
    fastio;
    memset(tree, 0, sizeof(tree));
    memset(arr, 0, sizeof(arr));

    int n, m;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    init(0, n - 1, 1);
    
    cin >> m;
    for(int i = 0; i < m; i++){
        int query_start, query_end;
        cin >> query_start >> query_end;
        cout << max_query(0, n - 1, query_start - 1, query_end - 1, 1).max << "\n";
    }

    return 0;
}