tree set / map1 [백준 14427] 수열과 쿼리 15 (Gold II) https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 세그먼트 트리 풀이가 정해라고 알려져 있다. 이 글에서는 Tree set 풀이를 다룬다. Tree set 풀이는 Red-black Tree로 구현한 set/map 자료구조가 O(log n) 속도로 최솟값 또는 최댓값을 찾아줄 수 있다는 성질을 이용한다. Red-black Tree는 max height O(log n)을 보장하기는 하지만 세그먼.. 2022. 10. 18. 이전 1 다음
