[문제풀이] 14706번: 구간 합 최대

[문제풀이] 14706번: 구간 합 최대

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

문제유형

세그먼트 트리

Solution

#include <stdio.h>
#define MAXN 50000
#define MAXT (50000*2*2)
int N, Q;    //원소의 갯수, 구간의 갯수
int tree[MAXT];
#define MAX(a,b) ((a > b) ? (a) : (b))
 
void update_new_data(int node, int s, int e, int idx, int d)
{
    int m;
 
    if (s == e)
    {
        tree[node] = d;
        return;
    }
 
    m = (s + e) / 2;
    if (idx <= m) update_new_data(node * 2, s, m, idx, d);
    else update_new_data(node * 2 + 1, m + 1, e, idx, d);
 
    tree[node] = MAX(tree[node * 2], tree[node * 2 + 1]);
}
 
int query(int node, int s, int e, int qs, int qe)
{
    int m;
    int left, right;
 
    if (qs <= s && e <= qe)
    {
        return tree[node];        
    }
    else if (s > qe || e < qs) return 0;
    
    m = (s + e) / 2;
    left = query(node * 2, s, m, qs, qe);
    right = query(node * 2 + 1, m + 1, e, qs, qe);
 
    return MAX(left, right);
}
 
int main()
{
    int i, j;
    scanf("%d %d", &N, &Q);
    for (i = 1; i <= N; i++)    //데이터 입력반기.
    {
        int input = 0;
        scanf("%d", &input);
        update_new_data(1, 1, N, i, input);
    }
    for (i = 0; i < Q; i++)        //구간의 최댓값 구하기.
    {
        int start = 0, end = 0;
        scanf("%d %d", &start, &end);
        printf("%d\n", query(1, 1, N, start, end));
    }
 
    return 0;
}