303. Запрос суммы диапазона, неизменяемый (Range Sum Query - Immutable)

Задание.

Получен целочисленный массив nums, обработайте несколько запросов следующего типа:

Вычислите сумму элементов nums между индексами left и right включительно, где left <= right.

Реализуйте класс NumArray:

• NumArray(int[] nums) Инициализирует объект целочисленным массивом nums.

• int sumRange(int left, int right) Возвращает сумму элементов в nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример 1.

Входные данные: [“NumArray”, “sumRange”, “sumRange”, “sumRange”] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Результат: [null, 1, -1, -3]

Пояснение:

NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Решение.

class NumArray {
private:
    vector<int> preSum;
public:
    NumArray(vector<int>& nums) {
        preSum.push_back(nums[0]);
        for (int i = 1; i < nums.size(); ++i)
            preSum.push_back(nums[i]+preSum[i-1]);
    }
    
    int sumRange(int left, int right) {
        if (left == 0) return preSum[right];
        return preSum[right] - preSum[left-1];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */

Другие задачи

304. Запрос суммы диапазона (Range Sum Query 2D - Immutable)

307. Запрос суммы диапазона, неизменяемый (Range Sum Query - Mutable)