백준 14428 수열과 쿼리 16 풀이 — 세그먼트 트리 (C++)

백준 14428번 ‘수열과 쿼리 16’은 점 갱신과 구간 최솟값의 인덱스 조회를 처리하는 세그먼트 트리 문제입니다.

각 노드에 (값, 인덱스)를 저장하면 값이 같을 때 더 작은 인덱스를 선택하는 조건까지 한 번에 해결할 수 있습니다. 트리 구성은 O(N), 각 갱신과 구간 조회는 O(log N)에 동작합니다.

14428번: 수열과 쿼리 16

---

풀이 아이디어

값과 인덱스를 함께 저장하기

세그먼트 트리의 각 노드에 구간의 최솟값만 저장하면 같은 값이 여러 개일 때 어느 인덱스를 출력해야 하는지 알 수 없습니다. 그래서 각 노드에 pair<int, int>{값, 인덱스}를 저장합니다.

C++의 pair 비교는 첫 번째 값부터 비교하고, 첫 번째 값이 같으면 두 번째 값을 비교합니다. 따라서 두 자식 노드 중 min을 선택하면 값이 더 작은 항목이 선택되고, 값이 같을 때는 인덱스가 더 작은 항목이 자동으로 선택됩니다.

갱신과 구간 조회

1번 쿼리는 해당 인덱스의 리프 노드를 바꾼 뒤 루트까지 올라가며 부모 노드를 다시 계산합니다. 2번 쿼리는 범위 밖의 구간에서 (INF, INF)를 반환하고, 범위 안에 완전히 포함된 구간에서는 저장된 값을 반환합니다. 일부만 겹치는 경우 두 자식의 결과 중 더 작은 pair를 선택합니다.

시간 복잡도: 초기 트리 구성 O(N), 값 갱신 O(log N), 구간 조회 O(log N)입니다. 트리 배열은 O(N)의 공간을 사용합니다.

---

C++ 구현

#include<bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
int n, m;

int arr[100001];
pair<int, int> tree[400004];

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

pair<int, int> find(int start, int end, int left, int right, int cur) {
    if(start > right || end < left) return {INF, INF};
    if(left <= start && end <= right) return tree[cur];
    int mid = (start+end)/2;
    return min(find(start, mid, left, right, cur*2), find(mid+1, end, left, right, cur*2+1));
}

void update(int start, int end, int idx, int val, int cur) {
    if(start > idx || end < idx) return;
    if(start == end) {
        tree[cur] = {val, idx};
        return;
    }
    int mid = (start+end)/2;
    update(start, mid, idx, val, cur*2);
    update(mid+1, end, idx, val, cur*2+1);
    tree[cur] = min(tree[cur*2], tree[cur*2+1]);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    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 a, b, c;
        cin >> a >> b >> c;
        
        if(a == 1) {
            update(0, n-1, b-1, c, 1);
        }
        else {
            cout << find(0, n-1, b-1, c-1, 1).second+1 << '\n';
        }
    }
}

 

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐