https://www.acmicpc.net/problem/14438
14438번: 수열과 쿼리 17
길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을
www.acmicpc.net
세그먼트트리 문제다.
풀이
구간의 최솟값이 담기는 세그먼트트리를 구현, 출력과 갱신을 담당하는 함수를 구현하여 접근하였다.
예제를 기준으로 만든 세그먼트 트리다. 리프노드부터 더 작은 값을 부모노드로 결정하여 만들면 된다. 트리의 갱신을 하게 된다면 가장 먼저 리프노드 값의 갱신이 이루어지고, 해당 노드부터 루트노드까지의 대소비교를 진행하면서 새로운 값으로 갱신을 해주면 된다.
재귀호출을 통해 갱신이 이루어지는데, 해당 호출 범위가 갱신인덱스가 포함되지 않는 구간이라면, 바로 해당 노드의 값을 반환하여 반대편 구간과의 대소비교를 진행하면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [5676] 음주 코딩 (0) | 2023.02.23 |
|---|---|
| [18436] 수열과 쿼리 37 (0) | 2023.02.21 |
| [1306] 달려라 홍준 (0) | 2023.02.18 |
| [14428] 수열과 쿼리 16 (0) | 2023.02.17 |
| [11505] 구간 곱 구하기 (0) | 2023.02.16 |