백준 - 최솟값 (10868)

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (N, M) = (input[0], input[1])

// 세그먼트 트리 구축
let height = ceil(log2(Double(N)))
let size = Int(pow(2.0, height + 1.0))
var tree = Array(repeating: Int.max, count: size + 1)

// 원본 데이터 넣기
for i in 0..<N {
    let index = Int(pow(2.0, height)) + i
    let input = Int(readLine()!)!
    tree[index] = input
}

// 부분 최솟값 저장
var index = size

while index != 1 {
    tree[index / 2] = min(tree[index / 2], tree[index])
    index -= 1
}

// 질의 수행
for _ in 0..<M {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    var startIndex = input[0] + Int(pow(2.0, height)) - 1
    var endIndex = input[1] + Int(pow(2.0, height)) - 1
    var minValue = Int.max
    
    while startIndex <= endIndex {
        if startIndex % 2 == 1 { minValue = min(minValue, tree[startIndex]) }
        if endIndex % 2 == 0 { minValue = min(minValue, tree[endIndex]) }
        startIndex = (startIndex + 1) / 2
        endIndex = (endIndex - 1) / 2 
    }
    print(minValue)
}

최솟값을 구하는 세그먼트 트리를 구현하는 문제였다. 이 문제에서는 데이터의 업데이트는 이뤄지지 않기 때문에 트리를 구축하고 질의를 수행하는 부분만 구현하면 된다.