給定一個整數數組 nums，處理以下類型的多個查詢:

計算索引 left 和 right （包含 left 和 right）之間的 nums 元素的 和 ，其中 left <= right
實現 NumArray 類：

NumArray(int[] nums) 使用數組 nums 初始化對象
int sumRange(int i, int j) 返回數組 nums 中索引 left 和 right 之間的元素的 總和 ，包含 left 和 right 兩點（也就是 nums[left] + nums[left + 1] + … + nums[right] )

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/range-sum-query-immutable
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
我寫的：

class NumArray {int[] nums;public NumArray(int[] nums) {this.nums = nums;}public int sumRange(int left, int right) {int sum = 0;for(int i = left;i<=right;i++){sum += nums[i];}return sum;}
}

答案：
前綴和
預處理時O（n），查詢時O（1）

class NumArray {int[] preSum;public NumArray(int[] nums) {int n = nums.length;preSum = new int[n+1];for(int i = 0;i<n;i++){preSum[i+1] = preSum[i] + nums[i];//preSum[i+1]表示sum前i項之和}}public int sumRange(int left, int right) {return preSum[right+1]-preSum[left];}
}