[백준/C++][수열과 쿼리 17(14438번)]

문제

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

14438번: 수열과 쿼리 17

Solve

세그먼트 트리를 활용해서 풀었다.

init함수를 만들어서 트리를 초기화하고 update함수를 만들어서 수를 변경하였다. 그리고 query 함수는 구간의 가장 작은 값을 출력하는 함수이다. 

 

update를 할 때 만약 구간이 아니라면 현재 노드의 값을 반환 , 만약 start == end라면 바뀌는 값을 tree[node]에 넣어준다.

, 만약 start!=end라면 왼쪽 오른쪽 노드를 방문하여서 둘중 작은 값이 tree[node]의 값이 되고 그 값을 반환해준다. (반복)

 

query 에서 구간이 아니라면 INF(무조건 큰값)을 반환해준다. (이 값이 최소값이 아니라는 것 -> 구간 밖이기 때문에 판별할 필요가 없어서)

만약 구간 안에 있다면 현재 노드를 반환한다.

그외 경우는 왼쪽 오른쪽 노드를 방문하여서 작은 값을 찾아 반환해준다.

 

 

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <cstdio>
#define INF 1000000001
using namespace std;
vector<long long> tree_min;
vector<int> v;
long long init(int node,int start,int end){
    if(start == end){tree_min[node] = v[start]; return tree_min[node];}
    return tree_min[node] = min(init(node*2,start,(start+end)/2),init(node*2+1,(start+end)/2+1,end));
}
long long update(int node,int start,int end,int idx,int val){
    if(start>idx || end<idx){return tree_min[node];}
    if(start == end){return tree_min[node] = val;}
    else{
        return tree_min[node] = min(update(node*2,start,(start+end)/2,idx,val),update(node*2+1,(start+end)/2+1,end,idx,val));
    }
}
long long query(int node,int start,int end,int left,int right){
    if(left>end||right<start){return INF;}
    if(left<=start&&right>=end){
        return tree_min[node];
    }
    else{
        return min(query(node*2,start,(start+end)/2,left,right),query(node*2+1,(start+end)/2+1,end,left,right));
    }
}
int main(void){
    int N,M;
    cin >> N;
    v.resize(N);
    for(int i = 0;i<N;i++){scanf("%d",&v[i]);}
    int tree_size = (1<<((int)ceil(log2(N))+1));
    tree_min.resize(tree_size);
    init(1,0,N-1);
    cin >> M;
    for(int i = 0;i<M;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a == 1){
            v[b-1] = c;
            update(1,0,N-1,b-1,c);
        }
        else{
            printf("%lld\n",query(1,0,N-1,b-1,c-1));
        }
    }
}