引入

首先来看这样一个问题：

$\forall s\in[0,2^n-1]$，求 $\sum_{t \subseteq s} a_t$。

显然可以枚举子集做到 $O(3^n)$，但高维前缀和可以做到 $O(n2^n)$。

那么什么是高维前缀和呢？

我们先来看一些低维的前缀和，例如二维。

在求二维前缀和时，我们通常用容斥的方法来求，即

$$s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}$$

但事实上，我们还可以把二维前缀和分解成两次一维前缀和，分别对每一维求前缀和。

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

高维前缀和

高维前缀和的思路是类似的。

我们可以把求集合 $s$ 的子集和的过程看成求一个一共 $n$ 维，每一维大小为 2 的前缀和。

for(re int i=0;i<n;++i){
    for(re int s=0;s<(1<<n);++s){
        if((s>>i)&1) f[s]+=f[s^(1<<i)];
    }
}

代码中的 $f_s$ 表示集合 $s$ 的子集和。

阅读代码不难发现，我们事实上就是在干一件事：对每一个子集的每一维分别求前缀和。

因为是对每一维分别求，所以一定是先枚举维再枚举子集。

事实上，高维前缀和不止能维护前缀和，它可以维护任何半群信息。

所以在遇到需要维护一个集合的所有子集的所有子集的半群信息时，都可以用高维前缀和做。

例题

[ARC100E] Or Plus Max

下文定义 $\oplus$ 为按位或。

首先把 $i \oplus j \le k$ 的限制转化掉，所以考虑对每个 $k$ 分别计算。

设 $A_k=\max_{i \oplus j =k,i \neq j} a_i+a_j$，那么 $ans_k=\max_{i=1}^k A_i$。

但这个 $A_i$ 依旧不好算，我们考虑拓宽限制。

设 $B_k=\max_{i,j \subseteq k,i \neq j} a_i+a_j$，那么 $ans_k=\max_{i=1}^k B_i$。

这为什么是对的？$A_i$ 不一定等于 $B_i$ 啊？

这是因为 $i,j \subseteq k$ 是 $i \oplus j =k$ 的必要条件，是 $i \oplus j \le k$ 的充分条件。

所以 $i,j \subseteq k,i \neq j$ 的所有元素 $(i,j)$ 一定完全包含 $i \oplus j =k,i \neq j$ 的所有元素，且不包含 $i \oplus j >k$ 的任何元素，但可能会包含 $i \oplus j < k$ 的元素。

但这不影响，因为我们的答案是前缀 $\max$，所以统计到的答案依旧是对的。

那么现在问题变成了 $\forall k\in[1,2^n-1]$，求 $\max_{i,j \subseteq k,i \neq j} a_i+a_j$。

不难发现，我们的 $\max$ 一定是最大和次大相加得到，所以只需要对于所有 $k$，维护子集最大和次大即可。

这显然可以高维前缀和维护。

复杂度 $O(n2^n)$

#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=(1<<18)+10,inf=1e18;
int n,S;
pii f[maxn];
inline void upd(pii &a,pii b){
    if(b.fi>a.fi) a.se=max(a.fi,b.se),a.fi=b.fi;
    else a.se=max(a.se,b.fi);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;S=(1<<n)-1;
    for(re int i=0;i<=S;++i) cin>>f[i].fi,f[i].se=-inf;
    for(re int i=0;i<n;++i){
        for(re int s=0;s<=S;++s){
            if((s>>i)&1) upd(f[s],f[s^(1<<i)]);
        }
    }
    int ans=0;
    for(re int i=1;i<=S;++i) ans=max(ans,f[i].fi+f[i].se),cout<<ans<<'\n';
    return 0;
}

Vowels

光题意就理解了半天···

一个非常直接的想法：对于每一个单词，我们都枚举超集，然后贡献到超集上。

这里的贡献注意不要算重，所以需要容斥一下。

具体的，我们对每一个子集都枚举超集，然后加贡献时带上容斥系数。

设 $S$ 为单词长度，$V$ 为字符集大小，则总复杂度为 $O(n2^S2^V)$

但这样每次都枚举超集太浪费了，能不能优化？

所以我们可以这样：对于每一个单词，先把贡献加到子集上，然后最后一块算贡献。

这样就可以只枚举一次了。

最后算贡献的时候，事实上就是求每个子集的子集和，高维前缀和即可。

复杂度为 $O(n2^S+V2^V)$

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=(1<<24)+10,m=24,S=(1<<24)-1;
int n;
int f[maxn];
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;char c;
    for(re int i=1;i<=n;++i){
        int t=0,cnt=0;
        for(re int j=1;j<=3;++j) cin>>c,t|=(1<<(c-'a'));
        for(re int s=t;s;s=(s-1)&t){
            if(__builtin_popcountll(s)&1) ++f[s];
            else --f[s];
        }
    }
    for(re int i=0;i<m;++i){
        for(re int s=0;s<=S;++s){
            if((s>>i)&1) f[s]+=f[s^(1<<i)];
        }
    }
    int ans=0;
    for(re int s=0;s<=S;++s) ans^=(f[s]*f[s]);
    cout<<ans;
    return 0;
}

拓展

子集和能做，超集和呢？

事实上也很简单，子集和时我们是子集向自己贡献，那超集和只需要自己向子集贡献即可。

for(re int i=0;i<n;++i){
    for(re int s=0;s<(1<<n);++s){
        if((s>>i)&1) f[s^(1<<i)]+=f[s];
    }
}

前缀和能做，差分呢？

只需要符号变一下就行了。

也不难理解，毕竟前缀和的逆运算就是差分。

for(re int i=0;i<n;++i){
    for(re int s=0;s<(1<<n);++s){
        if((s>>i)&1) f[s]-=f[s^(1<<i)];
    }
}