1. 问题描述
DP34 前缀和
要点： 说白了，就是快速、多次求给定区间的元素和。我们有前缀和算法来专门解决这类问题。
2. 解题思路
2.1 暴力解法
直接遍历给定区间求和，然后返回。时间复杂度为 O(m*N)，其中 m 的值可达 10^5，数组长度也是 10^5，相乘得 10^10。不管用什么语言，写出来时间复杂度达到 10^10，必然超时！
2.2 优化解法
暴力解法不够快，我们用前缀和算法，快速求得区间元素的和。
前缀和的实质
提前计算数组的累积和，将多次区间和查询的时间复杂度从 O(n) 优化到 O(1)。
两步走策略
1. 预处理：创建出一个前缀和数组
- 第一步：创建两个数组 dp[n+1] 和 arr[n+1]。arr 输入要处理的数组，dp[i] 表示 arr 数组中前 i 个元素之和。
- 将给定数组从下标 1开始输入数组 arr[n+1]。
为什么要创建 n+1 大小的数组，不应该是 n 吗，为什么从下标 1 开始？
因为第 0 个位置要放置元素 0，方便第二步操作。
- 第二步：使用公式：dp[i] = dp[i-1] + arr[i] 配置前缀和数组。 为了避免 dp[i-1] 越界访问，我们才从下标 1 开始操作。
上述创建前缀和数组的操作，时间复杂度为 O(N)。
2. 使用前缀和数组
我们求区间 [l, r] 的元素和，可以直接用 dp[r] - dp[l-1]。
使用前缀和数组的操作时间复杂度是 ，m 次也就是 。
