Range Sum Query - Immutable

Условие

Дан массив целых чисел nums, определите класс NumArray, который будет иметь методы для получения суммы элементов в диапазоне [i, j], где 0 <= i <= j < nums.length.

Примеры

Input:
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output: [null, 1, -1, -3]

Explanation:

val numArray = NumArray(intArrayOf(-2, 0, 3, -5, 2, -1))
numArray.sumRange(0, 2) // return 1 (-2 + 0 + 3)
numArray.sumRange(2, 5) // return -1 (3 + -5 + 2 + -1)
numArray.sumRange(0, 5) // return -3 (-2 + 0 + 3 + -5 + 2 + -1)

Решение

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = NumArray(nums)
 * var param_1 = obj.sumRange(left,right)
 */
class NumArray(nums: IntArray) {
    // Префиксный массив для хранения сумм
    private val prefixSum: IntArray = IntArray(nums.size + 1)

    init {
        // Заполняем префиксный массив
        for (i in nums.indices) {
            prefixSum[i + 1] = prefixSum[i] + nums[i]
        }
    }

    // Метод для получения суммы в диапазоне [i, j]
    fun sumRange(left: Int, right: Int): Int {
        // Возвращаем сумму в диапазоне, используя префиксный массив
        return prefixSum[right + 1] - prefixSum[left]
    }
}

Временная сложность

O(n) для инициализации и O(1) для каждого вызова sumRange.

Пространственная сложность

O(n) — используется дополнительный массив для хранения префиксных сумм.