高维前缀和

HeJie2026-04-292026-09-17

高维前缀和是对一维、二维前缀和的多维数据结构的推广。

核心求解思想：逐维前缀和

在了解高维前缀和之前，需要先学习逐维前缀和的实现。

我们一般用容斥原理来构建二维前缀和，但还有一种基础的做法，是逐维前缀和。它的做法是，先对一行或者一列做前缀和，然后再对另一维度做前缀和，这样，可以得到二维前缀和。

对于这种逐一维度做前缀和的做法，我们叫它逐维前缀和。推广一下，可以发现，这个做法也可以应对更多维度的数据结构。

概述

对于维的数组，大小为，其前缀和定义为

高维前缀和常用于解决二进制中的问题，大概因为二进制的维度（位）比较多，但是大小（两种选择：0 和 1）却比较小，从时间以及空间复杂度来说最利于做成算法题吧。

在算法竞赛中，高维前缀和常用来解决的问题是 子集和（sum over subsets, SOS） 问题。

就是指，用高维前缀和来得到二进制数的子集之和，例如，二进制数 11，其子集有 00 01 10 11，求得这几个子集的贡献之和。

这时我们发现，这似乎和动态规划中的状压DP有点像，没错，其实这个问题是状压DP的一种，所以这种问题也叫 SOS DP。

因此，高维前缀和是解决特定状压DP问题的技巧。

例题

Codeforces 165E - Compatible Numbers

给定一个长度为（）的数组。对于数组中的每一个元素，你需要在这个数组中找到另一个元素，使得。如果找不到，输出 -1。数据范围（约 22 个二进制位）。

这是一道高维前缀和的模板题，题目要求找到与其互异的元素（任意一个），其实可以看作，找到其补集的子集。

也就是对于数字 x，找到其补集 ((1 << 22) - 1) ^ x 的子集元素，这道题中，我们可以定义一个高维前缀和，求子集元素中的最大值。

这样的话，初始化dp数组为，录入所有元素，让。

接下来，做逐维前缀和，先枚举一个维度，然后依次将这个维度的大的值（这一位为1）对小的（这一位为0）做前缀和，也就是找其它维度相同，只有此维度不同的做前缀最大值。这部分代码也是高维前缀和的模板代码。

for (int i = 0; i < 22; i ++) { // 枚举每一位
    for (int j = 0; j < (1 << 22); j ++) { //枚举所有集合
        if (j >> i & 1) {
            dp[j] = max(dp[j], dp[j ^ (1 << i)]); //做前缀和
        }
    }
}

做完前缀和之后，dp数组表示的就是一个数的子集元素最大是多少，只需要枚举每个元素，然后输出其补集的dp值就可以了。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n), dp(1 << 22, -1);
    for (auto &i : a) {
        cin >> i;
        dp[i] = i;
    }

    for (int i = 0; i < 22; i ++) {
        for (int j = 0; j < (1 << 22); j ++) {
            if (j >> i & 1) {
                dp[j] = max(dp[j], dp[j ^ (1 << i)]);
            }
        }
    }

    for (auto &i : a) {
        cout << dp[(1 << 22) - 1 ^ i] << ' ';
    }
    cout << '\n';

    return 0;
}

AtCoder ARC 100 E - Or Plus Max

给定一个大小为的数组。对于所有的从到，求出最大的（满足且）。

这道题和上一道做法是一样的，只是需要维护的不再是子集中最大的一个元素，而是最大的两个元素。

因此我们只要改变一下存储和做前缀和的方式，就可以得到答案。注意，本题要找的是小于等于的所以，对集合也从小到大做一个前缀和。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(1 << n);
    vector<array<int, 2>> dp(1 << n, array<int, 2>{});

    for (int i = 0; i < (1 << n); i ++) {
        cin >> a[i];
        dp[i][0] = a[i];
    }

    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < (1 << n); j ++) {
            if (j >> i & 1) {
                for (int k = 0; k < 2; k ++) {
                    if (dp[j ^ (1 << i)][k] > dp[j][1]) {
                        dp[j][1] = dp[j ^ (1 << i)][k];
                        if (dp[j][0] < dp[j][1]) swap(dp[j][0], dp[j][1]);
                    }
                }
            }
        }
    }

    int mx = 0;
    for (int i = 1; i < (1 << n); i ++) {
        mx = max(mx, dp[i][0] + dp[i][1]);
        cout << mx << '\n';
    }

    return 0;
}

CSES - Bit Problem

给定个数的数组。对于数组中的每个数，求出数组中有多少个数满足：

（即是的子集）

（即是的超集）

（即和至少有一个二进制位同为 1）

对于这几种问题，都可以进行转化。

第一个问题，显然可以用高维前缀和维护子集的个数。

第二个问题，有两种做法，既可以维护一个后缀和得到答案，也可以用容斥原理，总数减去子集的个数之后，加上y等于x的个数。

第三个问题，可以用容斥原理，答案是x的补集的子集元素个数。

知道这些后，只需要维护一个子集个数的高维前缀和，以及记录每个元素的个数，可以得出答案。

Codeforces 449D - Jzzhu and Numbers

给定一个长度为的数组（）。求出有多少个非空子序列，使得子序列中所有元素的按位与（AND）结果为 0。

这是一道结合了容斥原理的题目，涉及了一个容斥原理的经典套路。

想要得出每个二进制数不重合的的组合方式显然不太现实，我们想到用容斥原理。用所有的组合方式减去有重合的组合方式。

我们可以用高维后缀和，得到至少有这些位为的元素有多少个，如果有个元素，则可以选择的方式有种。

接下来，我们用这个式子来得到答案：

$有个的方案数至少有个的方案数至少有个的方案数至少有个的方案数至少有个的方案数$

于是，对于每个高维后缀和得到的超集数量，代表的就是相互按位与之后，至少这些位为的个数。对的数量进行计数，如果的个数为偶数（），则答案加上这些方案数，如果是奇数，则答案减去这些方案数。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;
const int N = 1 << 20;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> dp(N), f(n + 1), a(n);
    for (auto &i : a) {
        cin >> i;
        dp[i] ++;
    }

    for (int i = 0; i < 20; i ++) {
        for (int j = N - 1; ~j; j --) {
            if (j >> i & 1) dp[j ^ (1 << i)] += dp[j];
        }
    }

    f[0] = 1;
    for (int i = 1; i <= n; i ++) {
        f[i] = f[i - 1] * 2 % mod;
    }

    ll ans = 0;
    for (int i = 0; i < N; i ++) {
        // 这里反直觉的没有去掉空集，因为根据二项式定理可以证明，空集产生的贡献为0
        // 这符合数学原理，但也可以依据直觉去掉空集
        if (__builtin_popcount(i) & 1) ans -= f[dp[i]];
        else ans += f[dp[i]];
        ans = (ans + mod) % mod;
    }
    cout << ans << '\n';

    return 0;
}