高维前缀和
全称 Sum Over Subset DP，意思是在子集上做求和的 dp。
非常直观的一个名称，我们如果使用类似的思想，能推广出超集 dp，FMT 和 FWT。
不过时间有限这里不提 FMT 和 FWT。
泛化ψ(｀∇´)ψ
SOSDP 通常解决以下的一类问题：
给定 \(2^n\) 个集合的权值 \(w_i\)。
你需要对每个集合求它的子集的权值和。
换句话说求 \(\forall i, \sum\limits_{j \subseteq i} w_j\)。
正常枚举子集暴力求和是众所周知的 \(O(3^n)\) 做法。
有一个奇妙的想法，我们设 \(dp(i, msk)\) 表示，考虑 \(msk\) 的所有子集中，只有低 \(i\) 位变化的子集和。
这么说有点抽象，给一个解释：
\(dp(2, (10011)_2) = w((10011)_2) + w((10010)_2) + w((10001)_2) + w((10000)_2)\)
然后考虑转移：
- 如果 \(msk\) 的第 \(i\) 位不为 \(1\)，那么 \(dp(i, msk) = dp(i - 1, msk)\)。
- 如果 \(msk\) 的第 \(i\) 位不为 \(0\)，那么 \(dp(i, msk) = dp(i - 1, msk) + dp(i - 1, msk \oplus 2^i)\)。
其实就考虑新增的这一位能带来的变化就行了（以 \(i\) 做为阶段）。
然后可以显然地滚动掉一维，写出代码：
1 2 3 4 5 | |
可以注意到超集和就是对 \(01\) 取反考虑。
所以就是：
1 2 3 4 5 | |
这东西实质上是做一个 \(n\) 维前缀和，然后这个 dp 就是每一维分开做了前缀和，
好像也有点抽象，具体来说就是，扫描每一层，然后你把对应位置 \(i\) 的贡献从上一层 (\(msk \oplus 2^i\) 此时在上一层) 加到这一层就行了。
例子ψ(｀∇´)ψ
这个例子是 Lk 的杂题选讲里有的，这里就顺带着补了
给出序列 \(a\)，值域 \([0, 2\times 10^6]\)，长度为 \(n\le10^6\)。
你需要找到一对 \((i, j, k) \text{ s.t. } i < j < k\) 满足 \(a_i\operatorname{and}(a_j\operatorname{or}a_k)\) 最大，求出这个最大值。
枚举 \(a_i\)，贪心的考虑是否有两个在这个位置右边的数的 \(\text{or}\) 是当前答案的超集，更新就好了。
具体处理就考虑用 SOSDP 处理超集的信息就好，具体一点我等会来写。