一维前缀和：区间和查询

一、面试常考点

1. 为什么前缀和快

预处理一次，查询时只做一次减法。

2. 边界写法

常用长度 n+1 的 pre，pre[0]=0。

二、细节介绍

1. 构建

pre[i+1] = pre[i] + nums[i]。

2. 查询

pre[r+1] - pre[l]。

三、示例代码

class NumArray {
  constructor(nums) {
    this.pre = Array(nums.length + 1).fill(0)
    for (let i = 0; i < nums.length; i++) {
      this.pre[i + 1] = this.pre[i] + nums[i]
    }
  }

  sumRange(l, r) {
    return this.pre[r + 1] - this.pre[l]
  }
}

四、常用应用场景

1. 频繁区间统计

日志、交易、监控时序区间求和。

2. 算法预处理

给二分、DP、滑动窗口提供 O(1) 区间信息。