➕ 前缀和 — 区间求和的捷径

📖 前缀和的核心概念

前缀和（Prefix Sum）是一种预处理技巧，通过计算数组前 i 个元素的和，将任意区间 [left, right] 的求和从 O(n) 降为 O(1)。前缀和的思想可以推广到二维（矩阵区域和）和差分（区间修改），是解决区间问题的核心武器。

1. 前缀和的变体

2. 前缀和的通用模板

# 一维前缀和构建
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + nums[i]

# 区间查询 [left, right]
def range_sum(left, right):
    return prefix[right + 1] - prefix[left]

🎯 题目一：区域和检索 - 数组不可变 (LC 303)

题目描述：给定一个整数数组 nums，处理多个请求，求区间 [left, right] 内所有元素的和。

思路分析

代码实现

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

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]

复杂度分析

构建：O(n) | 查询：O(1)

空间复杂度：O(n)

变体练习

• LC 304 二维区域和检索 - 矩阵不可变
• LC 307 区域和检索 - 数组可修改（树状数组/线段树）

🎯 题目二：和为 K 的子数组 (LC 560)

题目描述：给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的连续子数组的个数。

思路分析

代码实现

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        from collections import defaultdict
        count_map = defaultdict(int)
        count_map[0] = 1  # 哨兵：前缀和为0出现1次
        prefix_sum = 0
        count = 0
        for num in nums:
            prefix_sum += num
            count += count_map[prefix_sum - k]
            count_map[prefix_sum] += 1
        return count

复杂度分析

时间复杂度：O(n) — 一次遍历

空间复杂度：O(n) — 哈希表

变体练习

• LC 523 连续的子数组和（和为 k 的倍数）
• LC 974 和可被 K 整除的子数组

🎯 题目三：除自身以外数组的乘积 (LC 238)

题目描述：给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。请不要使用除法，且在 O(n) 时间复杂度内完成。

思路分析

代码实现

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n
        
        # 左侧乘积
        left = 1
        for i in range(n):
            answer[i] = left
            left *= nums[i]
        
        # 右侧乘积
        right = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right
            right *= nums[i]
        
        return answer

复杂度分析

时间复杂度：O(n) — 两次遍历

空间复杂度：O(1) — 不含输出数组

变体练习

• LC 135 分发糖果（左右两次遍历）
• LC 42 接雨水（左右最大值的前缀预处理）

📝 课后练习

1. LC 304 二维区域和检索（二维前缀和）
2. LC 523 连续的子数组和（前缀和+哈希）
3. LC 974 和可被 K 整除的子数组
4. LC 724 寻找数组的中心下标
5. LC 1480 一维数组的动态和（前缀和练习）

🔑 本课要点回顾

• 前缀和：一次预处理 O(n)，区间查询 O(1)
• 哨兵 prefix[0] = 0，统一边界处理
• 区间和：sum[left, right] = prefix[right+1] - prefix[left]
• 前缀和+哈希：统计满足条件的子数组数量
• 前缀积：左右两次遍历，O(1) 额外空间
• 二维前缀和：容斥原理，加两次减一次

📚 扩展阅读

• 《算法导论》第4章（前缀和与分治）
• 前缀和专题：LeetCode 前缀和标签
• 差分数组：前缀和的逆运算，区间修改 O(1)

🔬 差分数组 — 前缀和的逆运算

如果说前缀和是"求和"的加速器，那么差分数组就是"区间修改"的加速器。两者互为逆运算，配合使用威力巨大。

差分数组操作速查

# 构建差分数组
n = len(nums)
diff = [0] * n
diff[0] = nums[0]
for i in range(1, n):
    diff[i] = nums[i] - nums[i - 1]

# 区间 [l, r] 加 val: O(1)
def range_add(diff, l, r, val):
    diff[l] += val
    if r + 1 < len(diff):
        diff[r + 1] -= val

# 还原原数组: O(n)
def restore(diff):
    result = [diff[0]]
    for i in range(1, len(diff)):
        result.append(result[-1] + diff[i])
    return result