[백준][Kotlin] 2042번 구간 합 구하기

해당 문제는 세그먼트트리를 이용하면 통과 할 수 있는 문제였습니다.

 

세그먼트 트리는 구간 질의 (range query) 문제를 효율적으로 해결하기 위한 자료구조입니다.

구간 질의란, 배열이나 리스트와 같은 자료구조에서 주어진 범위에 속하는 값들을 찾는 문제를 의미합니다. 예를 들어, 주어진 배열에서 특정 구간의 합이나 최소값, 최대값 등을 구하는 문제가 구간 질의 문제에 해당됩니다.

세그먼트 트리는 주어진 배열을 트리 형태로 변환하여 구간 질의를 해결합니다. 이를 위해, 배열을 노드로 가지는 이진 트리를 만들고, 각 노드는 해당 구간의 합, 최소값, 최대값 등을 저장합니다. 이진 트리의 루트 노드는 전체 구간에 대한 질의 결과를 저장하며, 자식 노드들은 부모 노드의 구간을 반으로 나눈 구간에 해당하는 값을 저장합니다. 이러한 구조를 통해, 구간 질의에 필요한 값을 빠르게 계산할 수 있습니다.

세그먼트 트리는 배열의 크기에 대해 O(N log N)의 공간 복잡도와 O(log N)의 시간 복잡도를 가집니다. 따라서, 배열의 크기가 큰 경우에도 효율적으로 구간 질의 문제를 해결할 수 있습니다.

 

하기는 제가 작성한 코드와 제출 결과 입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashMap

lateinit var arr: LongArray
var arrlen = 1

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    var N = st.nextToken().toInt()
    var M = st.nextToken().toInt()
    var K = st.nextToken().toInt()


    while (arrlen < N) {
        arrlen *= 2
    }
    arr = LongArray(arrlen * 2) { 0 }

    repeat(N) {
        st = StringTokenizer(br.readLine())
        update(it,st.nextToken().toLong())
    }
    
    repeat(M+K){
        st = StringTokenizer(br.readLine())
        val check = st.nextToken().toInt()
        if( check == 1) update(st.nextToken().toInt()-1,st.nextToken().toLong())
        else bw.appendLine(query(st.nextToken().toInt()-1,st.nextToken().toInt()-1).toString())
    }

    bw.flush()
    bw.close()

}

fun update(idx: Int, num: Long){ // 인덱스 받을 때 +arrlen해서 받을 것
    var nidx = idx+arrlen
    arr[nidx] = num
    nidx /= 2

    while(nidx > 0){
        arr[nidx] = arr[nidx*2] + arr[(nidx*2) +1]
        nidx /= 2
    }

}

fun query(start:Int,end:Int):Long{
    var sum = 0L
    var left = start+arrlen
    var right = end+arrlen

    while(left <= right){
        if(left % 2 == 1){
            sum += arr[left]
        }
        if(right % 2 == 0){
            sum += arr[right]
        }
        left = (left+1)/2
        right = (right-1)/2
    }

    return sum
}