高维前缀和

我们知道一维前缀和的写法：，那么对于二维前缀和呢？
显然，根据容斥原理，我们有
%3Ds%7Bx_1%2Cy_1%7D-s%7Bx1%2Cy_1-1%7D-s%7Bx1%2Cy_1-1%7D%2Bs%7Bx1-1%2Cy_1-1%7D%0A#card=math&code=%5Coperatorname%7Bsum%7D%28x_1%2Cy_1%29%3Ds%7Bx1%2Cy_1%7D-s%7Bx1%2Cy_1-1%7D-s%7Bx1%2Cy_1-1%7D%2Bs%7Bx_1-1%2Cy_1-1%7D%0A&id=QI4Sv)
处理二维前缀和还可以这么写，但是三维，四维呢？这玩意搞起容斥岂不是逆天？
实际上，我们还有一个处理前缀和的方式：

int a[N][N], s[N][N];
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        s[i][j] = a[i][j];
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        s[i][j] += s[i - 1][j];
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        s[i][j] += s[i][j - 1];

这样处理是等价的（分维度处理前缀和，然后再合并），但是写起来更简单。

二进制与高维前缀和

我们来看一个例题：

有 件物品，第 件物品的权值为 ，多个物品组成一个集合，集合的权值为集合中所有物品权值的异或和。现在有 次询问，每次询问给定一个集合 ，求出集合 的所有子集的权值和，以及其所有超集的权值和。

这个题目看起来跟高维前缀和没任何关系，不是吗？
我们假设有三个物品，编号分别为1,2,3，价值分别为A,B,C。我们不妨令：

我们好像发现，我们可以通过对应下标为0或者1来决定某件物品选还是不选，从而得到对应的某个状态的权值。我们可以每次询问暴力枚举，但是这个复杂度是 #card=math&code=O%28m2%5En%29&id=A5vlU) 的。
那么，前缀和在这有啥含义呢？
我们做一次前缀和，有

某个状态的前缀和，其实就是该状态所有子集的权值之和！（不太看得明白的，可以二维模拟一下）
子集是前缀和，那么超集只要反着做一遍即可。
但显然，我们不可能开一个20维数组，能把手写麻。但是万幸的是，因为每一位只是0或者1，所以我们可以进行状态压缩，将其压进一个整数里面即可。若状态 是状态 的子集，那么有 。

状态压缩之后，稍微习惯一下，然后就可以当作普通的高维前缀和来做了。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 25, V = 1 << N;
int n, m, a[N];
LL pre[V], suf[V];
int main()
{
    //read
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    //build:建立f数组
    for (int j = 0; j < (1 << n); ++j) {
        int sum = 0;
        for (int i = 0; i < n; ++i)
            if (j & (1 << i)) sum ^= a[i];
        pre[j] = suf[j] = sum;
    }
    //pre & suf
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < (1 << n); ++j)
            if (j & (1 << i))
                pre[j] += pre[j ^ (1 << i)];
            else
                suf[j] += suf[j ^ (1 << i)];
    //query
    while (m--) {
        int k, v = 0;
        scanf("%d", &k);
        for (int i = 0, t; i < k; ++i) {
            scanf("%d", &t);
            v |= 1 << (t - 1);
        }
        printf("%lld %lld\n", pre[v], suf[v]);
    }
    return 0;
}

SOSDP

感谢heyuhhh的博客：高维前缀和总结（sosdp）。
SOSDP解决的是这样一类问题：

对于所有 ，求解 。

直接暴力枚举子集的话，复杂度是 #card=math&code=O%282%5En%2A2%5En%29&id=PPDZo)，也就是 #card=math&code=O%284%5En%29&id=Jgk4i) （严格讲，均摊后的复杂度是 #card=math&code=O%283%5En%29&id=Ty4UT)，但是反正不够优就完事了）。如果进行高维前缀和，就可以将复杂度压进 #card=math&code=O%28n2%5En%29&id=x7t44) 。
看起来有点玄学，其实就三行代码：

for (int i = 0; i < n; ++i)
    for (int j = 0; j < (1 << n); ++j)
        if (j & (1 << i)) f[j] += a[j ^ (1 << i)];

（其实和上面的高维前缀和就是一个东西

我们来看一个改造版的题目（题目来源：ARC100E）：

给定 个数，分别记为 。 对于每个 ，求出 的最大值，且

如果我们将条件改一下，变成 ，算出的答案记为 ，那么原题目的答案就变成了 的前缀最大值了。但是，这个条件依然不太可做。
我们再改一下，变成 ，这样条件肯定比 强，但是比 要弱，所以我们可以根据这个来求，然后做一次前缀最大值即可。
我们需要找出状态 的两个值最大的子状态，如果暴力的话，这个复杂度显然有点高，所以我们可以魔改一下原来的SOSDP板子，将求和转化为求最大值和次大值即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1 << 20;
int n, a[N];
int Max1[N], Max2[N];
void update(int j, int k) {
    //更新最大值
    if (Max1[j] <= Max1[k])
        Max2[j] = Max1[j], Max1[j] = Max1[k];
    //更新次大值
    else if (Max2[j] <= Max1[k])
        Max2[j] = Max1[k];
}
int main()
{
    //read
    scanf("%d", &n);
    for (int i = 0; i < (1 << n); ++i)
        scanf("%d", &a[i]);
    //init
    for (int i = 0; i < (1 << n); ++i)
        Max1[i] = a[i], Max2[i] = -1e9;
    //pre
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < (1 << n); ++j)
            if (j & (1 << i)) update(j, j ^ (1 << i));
    //output
    int ans = 0;
    for (int i = 1; i < (1 << n); ++i) {
        ans = max(ans, Max1[i] + Max2[i]);
        printf("%d\n", ans);
    }
    return 0;
}