区间求和问题的简单总结

首先定义一下什么是 “区间求和问题”。
此类问题通常以数组作为输入，要求统计数组中所有非空区间（子数组）的 “状态” 之和。
我们知道，一个长为 n 的数组共有 n * (n + 1) / 2 个不同的非空子数组，如果暴力枚举的话时间复杂度至少为 O(n^2)，必然超时（如果能暴力过的话就没意义了），因此需要采取一些巧妙的办法来降低时间复杂度。

对于上述问题，我总结出了两种常用思路：
① 直接计算法
② 贡献法

先从直接计算法开始介绍。
请看这道题（这是我之前为了练习出题所出的）：

给你一个数组，你需要求出所有子数组和的总和。
举个例子，如果数组是 [1, 3, 5]，那么答案是 (1) + (3) + (5) + (1 + 3) + (3 + 5) + (1 + 3 + 5) = 30 。
考虑暴力做法。直接暴力枚举所有的子数组，需要 O(n^2) 的时间，统计该子数组的和，又需要 O(n) 的时间，因此总共需要 O(n^3) 的时间。
如果使用前缀和进行优化，可以把时间复杂度降低至 O(n^2)，但依然无法通过本题。

如何优化？不妨思考暴力做法的计算过程。
对于每一个下标 i (0 <= i < n)，我们都需要遍历另外一个下标 j，且 0 <= j <= i，分别以 j、i 作为子数组的左端点和右端点，计算出该子数组的和，然后加到最终答案上去——对于固定的 i，因为左端点可取 0, 1, ..., i，所以这样的子数组一共有 i + 1 个。
（也可以把 i 作为左端点，j 作为右端点，此时 i <= j < n，后续分析过程类似）
有没有什么办法，能不用反复地枚举 i + 1 个左端点呢？

受到 Kadane 算法（求最大子段和的算法之一）的启发，我们可以这样思考：
在所有 “以下标 i - 1 为右端点的子数组” 的右边连接下标为 i 的元素，就得到了所有以下标 i 为右端点的子数组……这么说并不完全对，因为这样只有 i 个子数组。
还需要考虑下标为 i 的元素本身——它构成了长度为 1 的子数组。

定义 dp[i] = 以下标 i 为右端点的所有子数组和的总和
根据上述分析，可以得到 dp[i] = dp[i - 1] + i * v[i] + v[i]，边界条件 dp[-1] = 0，而最终答案就等于 dp[0] + dp[1] + ... + dp[n - 1] 。

这就是直接计算法。它从已有的暴力法出发，利用状态之间的重叠实现已有结果的复用，减少了重复计算，从而优化最终的时间复杂度。

参考代码：

接下来介绍贡献法。
顾名思义，贡献法即考虑每个元素对最终答案的贡献。
那么在上述问题中，每个元素给最终答案的贡献是多少呢？是包含该元素的子数组个数。
考虑下标为 i 的元素，共有多少个子数组包含该元素呢？
这是一个分步乘法问题。首先考虑所有可能的左端点，可取 0, 1, 2, ..., i，共 (i + 1) 个；然后考虑所有可能的右端点，可取 i, i + 1, i + 2, ..., n - 1，共 (n - i) 个，所以当前元素的贡献为：
(i + 1) * (n - i) * v[i] 。
参考代码：

注意这里需要开 unsigned long long，因为我构造了一组测试数据来卡 long long。
尽管 long long 溢出不太常见，但还是要提防。

然后来看 lz 今天遇到的题目（题号是 abc371_e）：

这道题依旧给你一个数组，让你求出所有子数组中的互异元素数量的总和。

首先尝试用直接计算法解这道题。
同样，我们思考从 “以下标 i - 1 为右端点的子数组” 到 “以下标 i 为右端点的子数组” 的转移。
为了方便描述，定义 dp[i][j] 为子数组 (v[j], v[j + 1], .., v[i]) 中互异元素的数量。
不难得到 dp[i][j] = dp[i - 1][j] + X，其中 X = 1，如果 v[i] 在 (v[j], v[j + 1], .., v[i - 1]) 中未出现；否则为 0。
上述转移方程要求 0 <= j < i，因为当 j = i 时，(v[j], v[j + 1], .., v[i - 1]) 是不存在的，此时 dp[i][j] = dp[i][i] = 1 。
那么，“以下标 i 为右端点的子数组” 对最终答案的贡献就是：
dp[i][0] + dp[i][1] + ... + dp[i][i - 1] + 1

不妨把转移方程代入上式，得到：
Si = dp[i][0] + dp[i][1] + ... + dp[i][i - 1] + 1 =
(dp[i - 1][0] + 0) + (dp[i - 1][1] + 0) + ... + (dp[i - 1][k] + 0) + (dp[i - 1][k + 1] + 1) + (dp[i - 1][k + 2] + 1) + ... + (dp[i - 1][i - 1] + 1) + 1 =
(dp[i - 1][0] + dp[i - 1][1] + ... + dp[i - 1][k] + dp[i - 1][k + 1] + dp[i - 1][k + 2] + ... + dp[i - 1][i - 1]) + (0 + 0 + ... + 0 + 1 + 1 + ... + 1) + 1
注意，X 的取值是存在单调性的：想象子数组 (v[j], v[j + 1], .., v[i - 1]) 的左端点 j 逐渐向左边扩展的过程，j 越小，子数组就越长，越有可能把 v[i] 包括在里面。
于是有 Si = Si-1 + X' + 1，这里 X' = (0 + 0 + ... + 0 + 1 + 1 + ... + 1)。
换言之，我们只需要计算出 X'，即到底有多少个 X 取了 1，就能计算出 Si

怎么计算？
X 的定义是 “X = 1，如果 v[i] 在 (v[j], v[j + 1], .., v[i - 1]) 中未出现；否则为 0。”
我们可以用哈希表维护 v[i] 最后出现的下标 last，且 -1 <= last < i，若 last 为 -1 则说明 v[i] 之前没有出现过，那么 X 为 1 时，j 应该取在区间 [last + 1, i - 1] 里，共有 i - last - 1 种取值。
注意，这里的边界值是经过精心选择的——当 last 为 -1 时也依然符合 X 的定义，如果设成别的值，就需要额外的判断逻辑。

这样一来，我们就能计算出最终答案 S0 + S1 + ... + Sn-1 了。
参考代码：