> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/303-qu-yu-he-jian-suo-shu-zu-bu-ke-bian.md).

# \[303]\[简单]\[动态规划]\[前缀和] 区域和检索 - 数组不可变

## 题目描述

[303. 区域和检索 - 数组不可变](https://leetcode-cn.com/problems/range-sum-query-immutable/)

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

NumArray(int\[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums\[i], nums\[i + 1], ... , nums\[j])）

示例：

```
输入：
["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 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))
```

提示：

* 0 <= nums.length <= 104
* -105 <= nums\[i] <= 105
* 0 <= i <= j < nums.length
* 最多调用 104 次 sumRange 方法

## 解题思路

使用前缀和, 记录包含当前位置数字在内的, 之前所有数字的和. 求前缀和使用动态规划的方法. 在得到前缀和之后, 求任意两点之间的元素总和, 就可以使用对应的前缀和相减得到.

有个技巧是在存储前缀和的列表中, 在最前面的位置添加一个0, 这样在求前缀和之差的时候, 就不用考虑边界情况, 减少了代码的复杂度.

```python
class NumArray:
    def __init__(self, nums: List[int]):
        self.prefix = [0]
        for num in nums:
            self.prefix.append(self.prefix[-1] + num)

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

## 相关题目

* [\[304\]\[中等\]\[动态规划\]\[前缀和\] 二维区域和检索 - 矩阵不可变](/garnet/suan-fa/dong-tai-gui-hua/304-er-wei-qu-yu-he-jian-suo-shu-zu-bu-ke-bian.md)