区间和检索算法（前缀和算法）

题目描述
给定一个整数数组，你需要实现一个类，该类支持以下两种操作：

1. 在初始化时接收整数数组。
2. 提供一个方法，能够快速计算数组中从索引 i 到索引 j（包含两端）的元素总和。

示例
输入：
数组 [-2, 0, 3, -5, 2, -1]
查询 sumRange(0, 2) → 返回 -2 + 0 + 3 = 1
查询 sumRange(2, 5) → 返回 3 + (-5) + 2 + (-1) = -1

解题过程

步骤1：暴力法的局限性
最直接的方法是每次查询时遍历区间 [i, j] 并累加元素：

def sumRange(i, j):
    total = 0
    for index in range(i, j+1):
        total += nums[index]
    return total

• 问题：如果数组长度为 n，查询次数为 m，时间复杂度为 O(m*n)，当 n 和 m 很大时效率极低。

步骤2：引入前缀和思想
核心思路是预处理数组，将区间和问题转化为前缀和的差值：

1. 定义前缀和数组 prefix，其中 prefix[k] 表示原数组前 k 个元素的和（索引从0开始）。
   • 例如，对于数组 nums = [a0, a1, a2, ..., a_{n-1}]：

     prefix[0] = 0
     prefix[1] = a0
     prefix[2] = a0 + a1
     ...
     prefix[n] = a0 + a1 + ... + a_{n-1}
     

2. 区间 [i, j] 的和可以表示为：

   sumRange(i, j) = prefix[j+1] - prefix[i]
   

   • 因为 prefix[j+1] 包含前 j+1 个元素（索引0到j），而 prefix[i] 包含前 i 个元素（索引0到i-1），两者相减正好是索引 i 到 j 的和。

步骤3：具体实现
以示例数组 [-2, 0, 3, -5, 2, -1] 为例：

1. 构建前缀和数组：

   prefix[0] = 0
   prefix[1] = -2
   prefix[2] = -2 + 0 = -2
   prefix[3] = -2 + 0 + 3 = 1
   prefix[4] = 1 + (-5) = -4
   prefix[5] = -4 + 2 = -2
   prefix[6] = -2 + (-1) = -3
   

2. 计算 sumRange(0, 2)：

   prefix[3] - prefix[0] = 1 - 0 = 1
   

3. 计算 sumRange(2, 5)：

   prefix[6] - prefix[2] = -3 - (-2) = -1
   

步骤4：代码实现

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

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

步骤5：复杂度分析

• 初始化：O(n)，需遍历数组一次。
• 查询：O(1)，仅需一次减法操作。
• 空间复杂度：O(n)，用于存储前缀和数组。

总结
前缀和算法通过预处理将区间和查询的耗时从 O(n) 优化到 O(1)，适用于查询频繁的场景。其核心是理解“区间和等于前缀和差值”的转换思想。