문제 요약
이 문제는 N 개의 수에 구간 곱을 구하는 것인데
구간 곱을 구하는 중간 중간에 값의 변화가 일어나는 상황에서 구간 곱을 효율적으로 구해야 하는 문제이다.
문제 접근
세그멘트 트리
만약 이전에 했던 것 처럼 구간 합 또는 곱을 구하는 방식을 생각해본다면 N개의 배열을 만들어서
구간 곱을 만들어서 진행하였을 것이다
ex) 1, 2, 3, 4, 5
=> 구간 곱 배열 1, 2, 6, 24, 120
이렇게 구간 곱 배열을 미리 정의 해두고 하는 것도 효율적인 방법이지만 중요한 점은 중간에 값 변화가 일어난다는 것이다.
값 변화가 m번 즉, 최대 10000 번 까지 일어날 수 있는데 이런식으로 구간 곱에다가 변화를 적용하면 어떠한 값 변화로 인해 최악의 경우 전체 배열에 대해 그러한 변화를 적용해야 하기 때문에 n * m 번의 연산이 소유된다.
따라서 이렇게 접근하면 안되고 다른 방법이 필요하다.
세그멘트 트리는 이러한 상황에서 굉장히 효율적이기 때문에 세그멘트 트리를 사용해서 이 문제를 접근하는 것이 좋다.
값 변화가 클 때 공간복잡도를 늘리는 대신 시간 복잡도를 줄이는 trade-off를 하는 것이다.
세그멘트 트리란?
세그먼트 트리는 여러 개의 데이터가 연속적으로 존재할 때, 특정 구간의 데이터를 합치는 연산(예: 합, 최대값, 최소값, 곱 등)을 빠르게 수행하기 위해 고안된 자료구조입니다. 이진 트리의 형태를 취하고 있으며, 각 노드가 하나의 구간을 대표하게 됩니다.
즉 이 문제에서 세그멘트 트리는 공간을 좀 더 사용하여 각 구간 곱을 세분하게 가지고 있는 것이다.
기존에는 연속된 부분의 구간 곱만을 사용하고 있어 하나의 변경이 뒤 구간 곱에 모두 영향을 주었지만 세그멘트 트리는 세분적으로 구간 곱을 가지고 있기 때문에 영향을 받는 구간 곱을 가지는 부분만 변경을 하면되어서 시간 복잡도가 줄어들게 된다.
세그멘트 트리에 대해서 간단히 설명 하기 위해
1,2,3,4,5를 예제로 살펴보자
초기 배열: 1, 2, 3, 4, 5
세그멘트 트리 구축
구축 단계에서는 두 개만 고려하면 된다.
1. 리프 노드는 배열의 각 요소를 나타낸다
2. 내부 노드는 자식 노드들의 곱을 저장한다.
[120]
/ \
[6] [20]
/ \ / \
[2] [3] [4] [5]
/ \
[1] [2] 리프 노드 1,2,3,4,5는 원본 배열의 각 요소가 위치한다.
각 노드는 구간 곱을 가지고 있다.
즉 리프노드는 자기자신의 구간 곱을 가지고 있는 것이다.
리프 노드가 아닌 부모노드는 자식 노드가 가지는 원본 배열의 구간 곱을 가지고 있다
아래 부분만 본다면
[6]
/ \
[2] [3]
/ \
[1] [2] 리프노드 1,2,3은 원본 배열 각각의 구간 곱을 가지고 있다
[1]과 [2]를 자식으록 가지는 부모노드 [2]는
인덱스 1,2의 구간 곱을 가지고 있고
[6]은 인덱스 1,2,3의 구간곱을 가지고 있다.
이런 와중에 만약 1번째 인덱스의 값이 6으로 변경되었다면 어떻게 될까?
3번째 구간을 포함하는 리프 노드의 값을 변경한 다음 그 부모 노드의 값을 계속 타고 올라가며 변경해주면 된다
// 리프노드 변경
[120]
/ \
[6] [20]
/ \ / \
[2] [3] [4] [5]
/ \
<6> [2] // 부모 노드 변경
[120]
/ \
[6] [20]
/ \ / \
<12> [3] [4] [5]
/ \
[6] [2]
[120]
/ \
<36> [20]
/ \ / \
[12] [3] [4] [5]
/ \
[1] [2]
<720>
/ \
[36] [20]
/ \ / \
[12] [3] [4] [5]
/ \
[1] [2]
5번 변경이 일어났던 것에서 4번 변경으로 줄어들었다.
지금은 n이 굉장히 작아서 큰 의미가 없지만 평균적으로 세그멘트 트리가 4*n의 크기로 구성된다고 가정하고
n이 1000000이라고하면
log 4000000 => 약 21번으로
총 (1000000 - 21)번 차이가 난다.
세그멘트 트리의 시간 복잡도는 아래와 같다.
구축 : O(N)
업데이트 : O(logN)
쿼리 : O(logN)
좀 더 구체적으로는 4N으로 계산 해주어야한다.
이처럼 세그먼트 트리는 구간 쿼리 문제를 해결하기 위한 강력한 자료구조로, 한 번 구축해 두면 다양한 구간 연산을 빠르게 처리할 수 있는 장점을 가지고 있습니다.
모듈러 연산
입력으로 주어지는 모든 수는 0보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.
구간 곱이 이루어질 때 특정 부분에서 굉장히 큰 값이 나올 수 있다.
따라서 문제에서는 구간의 곱을 1,000,000,007로 나눈 나머지를 출력하라고 한다.
따라서 세그멘트 트리를 구축할 때 모듈러 연산을 적용하면 된다.
주의 할점은 업데이트 및 쿼리를 할 때도 적용해야 하는 점이다.
업데이트는 쿼리를 다시 재구성하는 과정을 포함하기에 필수적이고 쿼리는 각 구간이 여러 노드에 걸쳐 표현될 수 있기에 필수적이다.
코드
import kotlin.collections.ArrayList
const val MOD = 1000000007
fun main() {
val br = System.`in`.bufferedReader()
val (n, m, k) = br.readLine().split(" ").map { it.toInt() }
val nums = ArrayList<Long>()
repeat(n) {
nums.add(br.readLine().toLong())
}
val sb = StringBuilder()
val segment = SegmentTree(nums.toLongArray())
repeat(k + m) {
val (a, b, c) = br.readLine().split(" ").map { it.toInt() }
// update
if (a == 1) {
segment.updateUtil(b, c)
}
// query
if (a == 2) {
sb.append(segment.queryUtil(b, c) % MOD).append("\n")
}
}
print(sb.toString())
}
class SegmentTree(val nums: LongArray) {
private val size = nums.size
private val tree = LongArray(4 * size) { 1L }
init {
build(0, size - 1, 0)
}
private fun build(start: Int, end: Int, idx: Int) {
if (start == end) {
tree[idx] = nums[start]
} else {
val mid = (start + end) / 2
build(start, mid, 2 * idx + 1)
build(mid + 1, end, 2 * idx + 2)
tree[idx] = (tree[2 * idx + 1] * tree[2 * idx + 2]) % MOD
}
}
fun updateUtil(b: Int, c: Int) {
update(0, size - 1, 0, b - 1, c.toLong())
}
private fun update(start: Int, end: Int, idx: Int, updateIdx: Int, updateValue: Long) {
if (updateIdx < start || updateIdx > end) return
if (start == end) {
tree[idx] = updateValue
nums[updateIdx] = updateValue
} else {
val mid = (start + end) / 2
update(start, mid, idx * 2 + 1, updateIdx, updateValue)
update(mid + 1, end, idx * 2 + 2, updateIdx, updateValue)
tree[idx] = (tree[2 * idx + 1] * tree[2 * idx + 2]) % MOD
}
}
fun queryUtil(b: Int, c: Int): Long {
return query(0, size - 1, 0, b - 1, c - 1) % MOD
}
private fun query(start: Int, end: Int, idx: Int, qs: Int, qe: Int): Long {
if (qs > end || qe < start) return 1
if (qs <= start && qe >= end) return tree[idx]
val mid = (start + end) / 2
return (query(start, mid, 2 * idx + 1, qs, qe) * query(mid + 1, end, 2 * idx + 2, qs, qe)) % MOD
}
}
코드는 초기에 이해하기 어려우나 한 단계식 따라가보면 이해할 수 있다
build의 경우 부모 노드(전체 리프 노드 전체 포함)부터 타고 내려가 start와 end가 동일한 즉 리프노드에 도달하는 경우에 해당 node에 값을 넣어주고 재귀를 통해 자식노드가 완료되면 다시 루트 노드로 되돌아가며 부모 노드도 갱신해주는 방법이다.
update의 경우 동일하게 루트노드부터 업데이트 해주려는 인덱스를 포함하는 자식노드를 계속 찾아 내려가면서 되돌아가면서 업데이트 해주는 방식이다. 인덱스를 포함하는 모든 노드는 값 변화에 영향을 받는 노드이다 라는 논리를 잘 생각해보자
query의 경우 동일하게 루트 노드부터 시작해 해당 쿼리 구간을 완전히 포함하는 노드가 나올 때 까지 자식을 들어가는 과정이다.
구간에서 완전히 벗어나면 1을 리턴 구간에 완전히 포함된다면 해당 노드를 반환하여 곱하면 된다.
[120]
/ \
[6] [20]
/ \ / \
[2] [3] [4] [5]
/ \
[1] [2] 만약 3~5까지 구간 곱을 원할때
// 루트노드는 |1~5|까지로 완전히 포함 x
[6]과 [20] 노드로 이동
<120>
/ \
[6] [20]
/ \ / \
[2] [3] [4] [5]
/ \
[1] [2] [6]의 경우 |1~3|으로 완전히 포함 x
[2]와 [3] 노드로 이동
[120]
/ \
<6> [20]
/ \ / \
[2] [3] [4] [5]
/ \
[1] [2] [2] 노드의 경우 |1~2|로 쿼리 범위에서 완전히 벗어남
return 1
[120]
/ \
[6] [20]
/ \ / \
<2> [3] [4] [5]
/ \
[1] [2]
[3] 노드의 경우 |3|으로 완전히 포함
return [3]
[120]
/ \
[6] [20]
/ \ / \
[2] <3> [4] [5]
/ \
[1] [2]
다시 돌아가서 [20]의 경우 |4-5|로 완전히 포함
return [20]
[120]
/ \
[6] <20>
/ \ / \
[2] [3] [4] [5]
/ \
[1] [2] return 값을 전체 곱해보면 60인것을 알 수 있다.
배운점
세그멘트 트리에 대해서 배웠다.
공간과 시간의 trade-off
