区间销售额统计

题目

区间销售额统计

信息

• 类型：问答
• 难度：⭐

考点

前缀和构建,区间和查询,数组操作

快速回答

使用前缀和数组高效解决区间求和问题：

• 构建前缀和数组 prefix，其中 prefix[i] = arr[0] + arr[1] + ... + arr[i-1]
• 查询区间 [L,R] 的和时，使用公式 prefix[R+1] - prefix[L]
• 时间复杂度：构建 O(n)，查询 O(1)；空间复杂度 O(n)

问题场景

某公司需要统计连续 N 天的销售额（存储在数组 sales 中）。设计一个系统，支持快速查询任意时间段 [start, end]（包含起止日期）的总销售额。

原理说明

前缀和的核心思想是预处理数组的累积和：

• 定义前缀和数组 prefix，其中 prefix[i] 表示原数组前 i 个元素的和
• 数学表示：prefix[0] = 0, prefix[i] = sales[0] + sales[1] + ... + sales[i-1]
• 区间和公式：sum(start, end) = prefix[end+1] - prefix[start]

代码示例

class SalesSystem:
    def __init__(self, sales):
        n = len(sales)
        self.prefix = [0] * (n + 1)
        # 构建前缀和数组
        for i in range(1, n + 1):
            self.prefix[i] = self.prefix[i-1] + sales[i-1]

    def query_range(self, start, end):
        # 查询区间和（包含 start 和 end）
        return self.prefix[end+1] - self.prefix[start]

# 示例用法
sales = [100, 200, 150, 300, 250]  # 第0天到第4天的销售额
system = SalesSystem(sales)
print(system.query_range(1, 3))  # 输出 650 (200+150+300)

最佳实践

• 边界处理：前缀和数组长度设为 n+1，索引0设为0，避免边界判断
• 查询效率：多次查询场景下，前缀和将单次查询复杂度从 O(n) 降至 O(1)
• 适用场景：静态数组的频繁区间求和（数据不变或少量更新）

常见错误

• 索引偏移错误：混淆原数组与前缀和数组的索引（如使用 prefix[end] - prefix[start-1]）
• 边界处理不当：未正确处理 start=0 的情况
• 空间浪费：使用二维数组而非一维前缀和解决一维问题

扩展知识

• 差分数组：前缀和的逆操作，用于高效区间修改（如给区间内所有值加常数）
• 二维前缀和：扩展至矩阵区域求和，公式：sum = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]
• 动态更新：若需支持数据修改，可结合树状数组或线段树实现