백준 - 구간 곱 구하기 (11505)

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (N, M, K) = (input[0], input[1], input[2])
let MOD = 1000000007
// 세그먼트 트리 초기화
let height = ceil(log2(Double(N)))
let size = Int(pow(2.0, height + 1))
var tree = Array(repeating: 1, count: size + 1)

setTree()

// 질의 수행
for _ in 0..<M+K {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    if input[0] == 1 {
        updateTree(input[1], input[2])
    } else {
        print(getMul(input[1], input[2]))
    }
}

func setTree() {
    // 원본 데이터 저장
    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] = tree[index / 2] * tree[index] % MOD
        index -= 1
    }
}

func updateTree(_ target: Int, _ value: Int) {
    var index = target + Int(pow(2.0, height)) - 1
    tree[index] = value
    while index > 1 {
        index = index / 2
        tree[index] = tree[index * 2] % MOD * tree[index * 2 + 1] % MOD
    }
}

func getMul(_ a: Int, _ b: Int) -> Int {
    var start = a + Int(pow(2.0, height)) - 1
    var end = b + Int(pow(2.0, height)) - 1
    var result = 1
    while start <= end {
        if start % 2 == 1 { result = result * tree[start] % MOD }
        if end % 2 == 0 { result = result * tree[end] % MOD }
        start = (start + 1) / 2
        end = (end - 1) / 2
    }
    return result
}

세그먼트 트리를 사용해서 구간 곱을 구하는 문제이다.

이 문제에서 신경써야 할 부분은 크게 두 가지이다.

1. 트리를 업데이트 할 때 일반적인 세그먼트 트리처럼 변화된 값만을 가지고 트리를 업데이트 하면 노드의 값이 0일 때는 업데이트가 제대로 이루어지지 않는다. 그래서 노드의 값을 업데이트 한 후 부모 노드로 거슬러 올라가면서 두 자식 노드의 값을 곱해주는 방식으로 업데이트를 해야 한다.
2. 각 노드의 값들이 1,000,000,007을 넘어가지 않도록 계속해서 모듈러 연산을 해준다. → 사실 이 부분 원리가 잘 이해가 되지 않는다..

원래 모듈러 연산을 포함하는 부분에서 tree[index / 2] *= tree[index] % MOD 이런 식으로 *= 연산자를 사용했더니 런타임 에러가 발생했다. 이 연산자를 사용하면 계산 순서가 의도했던 것과 달라져서 오버플로우가 발생하는 것이 원인인 것 같다.