一维数组区间和查询

题目

一维数组区间和查询

信息

• 类型：问答
• 难度：⭐

考点

前缀和概念,区间求和优化,基础算法实现

快速回答

使用前缀和数组优化区间和查询：

• 构建前缀和数组 prefix，其中 prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
• 查询区间 [l, r] 的和：prefix[r+1] - prefix[l]
• 时间复杂度：构建 O(n)，查询 O(1)

原理说明

前缀和是一种预处理技术，核心思想是用空间换时间。通过构建一个前缀和数组 prefix，其中每个元素 prefix[i] 存储原数组 nums 从索引 0 到 i-1 的元素和。这样可以将区间和查询从 O(n) 优化到 O(1)。

代码示例（Python）

class PrefixSum:
    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 query_range_sum(self, l, r):
        # 查询闭区间 [l, r] 的和
        return self.prefix[r + 1] - self.prefix[l]

# 使用示例
nums = [2, 1, 5, 3, 4]
ps = PrefixSum(nums)
print(ps.query_range_sum(1, 3))  # 输出 1+5+3=9
print(ps.query_range_sum(0, 4))  # 输出 2+1+5+3+4=15

最佳实践

• 边界处理：前缀和数组长度设为 n+1，prefix[0]=0 可统一查询逻辑
• 空间优化：当需要频繁查询时，预处理是值得的
• 适用场景：多次区间和查询、固定数组

常见错误

• 索引越界：查询时 r+1 可能超出范围（应确保 r < n）
• 区间定义混淆：prefix[r+1] - prefix[l] 对应闭区间 [l, r]
• 多次查询重复计算：未使用前缀和导致每次查询 O(n) 时间

扩展知识

• 差分数组：前缀和的逆操作，用于区间修改（如给 [l, r] 统一加值）
• 二维前缀和：扩展至矩阵区域求和，公式：
  sum = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]
• 动态维护：如果数组元素可变，考虑树状数组或线段树