算法模式：前缀和
💡
原文中文，约1600字，阅读约需4分钟。
📝
内容提要
前缀和是一种数组算法，通过预处理计算前 n 项的和，能有效降低查询时间复杂度。例如，LeetCode 303 中，使用前缀和将 sumRange 方法的复杂度降至 O(1)，但需要额外空间 O(n)。
🎯
关键要点
- 前缀和是一种数组算法，通过预处理计算前 n 项的和。
- 前缀和能有效降低查询时间复杂度，复杂度降至 O(1)。
- 使用前缀和需要额外空间 O(n)。
- LeetCode 303 示例中，使用前缀和计算数组元素的和。
- 最普通的解法是遍历相加，时间复杂度为 O(n)。
- 使用前缀和后，时间复杂度降低为 O(1)，但需要额外空间。
- NumArray 类实现了前缀和的功能。
- LeetCode 437 也使用了前缀和的技巧。
❓
延伸问答
前缀和算法的主要功能是什么？
前缀和算法通过预处理计算前 n 项的和，能有效降低查询时间复杂度。
使用前缀和算法的时间复杂度和空间复杂度分别是多少？
使用前缀和算法的时间复杂度为 O(1)，但需要额外的空间 O(n)。
在LeetCode中，前缀和算法是如何应用的？
在LeetCode 303中，前缀和用于计算数组元素的和，优化了查询效率。
前缀和算法与普通遍历相加的时间复杂度有什么区别？
普通遍历相加的时间复杂度为 O(n)，而前缀和的时间复杂度降低为 O(1)。
NumArray类是如何实现前缀和功能的？
NumArray类通过构造函数计算前缀和，并在sumRange方法中使用这些值进行快速查询。
前缀和算法的应用场景有哪些？
前缀和算法适用于需要频繁查询数组区间和的场景，如LeetCode 303和LeetCode 437等题目。
➡️
