백준 #2042 #Kotlin #구간 합 구하기

[구간 합 구하기]

구간 합 구하는 문제는 보통 세그먼트리나 펜윅트리로 풀게 된다.
펜윅트리의 원리를 알게되면 세그먼트리보다 간단하게 풀 수 있다.

fun main() {

    val br = System.`in`.bufferedReader()

    val (n, m, k) = br.readLine().split(" ").map { it.toInt() }
    val tree = Array(n + 1) { 0L }

    fun sum(idx: Int): Long {
        var result = 0L
        var i = idx
        while(i > 0) {
            result += tree[i]
            i -= i.and(-i)
        }
        return result
    }

    fun update(idx: Int, value: Long) {
        var i = idx
        while (i <= n) {
            tree[i] += value
            i += i.and(-i)
        }
    }

    (1..n).forEach {
        val number = br.readLine().toLong()
        update(it, number)
    }

    val sb = StringBuilder()
    repeat (m + k) {
        val (a, b, c) = br.readLine().split(" ").map { it.toLong() }
        if (a == 1L) {
            val num = sum(b.toInt()) - sum(b.toInt() - 1)
            update(b.toInt(), c - num)
        } else if (a == 2L) {
            sb.append(sum(c.toInt()) - sum(b.toInt() - 1)).append('\n')
        }
    }
    print(sb.toString())
}