303. Range Sum Query - Immutable

public class NumArray {
    private int[] sum;
    public NumArray(int[] nums) {
        sum = new int[nums.Length + 1];
        for (int i = 0; i < nums.Length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }
    public int SumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class NumArray {
    private vector<int>& sum;
    public NumArray(vector<int>& nums) {
        sum = new int[nums.size() + 1];
        for (int i = 0; i < nums.size(); i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }
    public int SumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

public class NumArray {
    private int[] sum;

    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

class NumArray {
    constructor(nums) {
        this.sum = new Array(nums.length + 1).fill(0);
        for (let i = 0; i < nums.length; i++) {
            this.sum[i + 1] = this.sum[i] + nums[i];
        }
    }

    sumRange(i, j) {
        return this.sum[j + 1] - this.sum[i];
    }
}

class NumArray:
    def __init__(self, nums: List[int]):
        self.sum = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.sum[i + 1] = self.sum[i] + nums[i]

    def sumRange(self, i: int, j: int) -> int:
        return self.sum[j + 1] - self.sum[i]

package main

type NumArray struct {
    sum []int
}

func Constructor(nums []int) NumArray {
    sum := make([]int, len(nums)+1)
    for i := 0; i < len(nums); i++ {
        sum[i+1] = sum[i] + nums[i]
    }
    return NumArray{sum}
}

func (this *NumArray) SumRange(i int, j int) int {
    return this.sum[j+1] - this.sum[i]
}

Algorithm

Инициализация:

Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.

Предварительное вычисление сумм:

Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

Вычисление диапазонной суммы:

Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎