前缀和

前缀和的定义与区间和公式是什么？

• 定义: prefixSum[i] = nums[0] + ... + nums[i], 与 nums 等长;
• 单项还原: nums[i] = prefixSum[i] - prefixSum[i-1];
• 区间和: nums[i..j] = prefixSum[j] - prefixSum[i-1];
• 不足: 区间左端点为 0 时需要特判 prefixSum[-1];

带哨兵的前缀和有什么好处？

• 定义: prefixSum[i] = nums[0] + ... + nums[i-1], 且 prefixSum[0] = 0, 长度比 nums 多 1;
• 单项还原: nums[i] = prefixSum[i+1] - prefixSum[i];
• 区间和: nums[i..j] = prefixSum[j+1] - prefixSum[i];
• 好处: 区间左端点为 0 时无需特判, 统一写成两个下标相减;

如何构造前缀和？

function buildPrefixSum(nums: number[]): number[] {
  const prefixSum = new Array(nums.length + 1);
  prefixSum[0] = 0;
  for (let i = 1; i <= nums.length; i++) {
    prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
  }
  return prefixSum;
}

前缀和的复杂度是多少？

• 预处理: O(n);
• 单次区间和查询: O(1);
• 空间复杂度: O(n);