算法模式：前缀和
💡
原文中文，约1600字，阅读约需4分钟。
📝
内容提要
前缀和是一种数组算法，通过预处理计算前 n 项的和，能有效降低查询时间复杂度。例如，LeetCode 303 中，使用前缀和将 sumRange 方法的复杂度降至 O(1)，但需要额外空间 O(n)。
🎯
关键要点
-
前缀和是一种数组算法，通过预处理计算前 n 项的和。
-
前缀和能有效降低查询时间复杂度，复杂度降至 O(1)。
-
使用前缀和需要额外空间 O(n)。
-
LeetCode 303 示例中，使用前缀和计算数组元素的和。
-
最普通的解法是遍历相加，时间复杂度为 O(n)。
-
使用前缀和后，时间复杂度降低为 O(1)，但需要额外空间。
-
NumArray 类实现了前缀和的功能。
-
LeetCode 437 也使用了前缀和的技巧。
➡️
