介绍

一维前缀和 : $ s[i] = s[i - 1] + a[i] $
二维前缀和: $s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] $

当然也可以这么写:

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];

\(n\) 维前缀和, 我们可以做 \(n\) 次一维前缀和，差不多这个样子， 跟二维前缀和是类似的。

for(int i[1] = 1; i[1] <= n; i[1]++)
    for(int i[2] = 1; i[2] <= n; i[2]++)
        //...
        a[i[1]][i[2]][i[3]] ... += a[i[1] - 1] ...;
for(int i[1] = 1; i[1] <= n; i[1]++)
    for(int i[2] = 1; i[2] <= n; i[2]++)
        //...
        a[i[1]][i[2]][i[3]] ... += a[i[1]][i[2] - 1] ...;
...

例题

Ⅰ. P5495 Dirichlet 前缀和

根据唯一分解定理，将每个素数看成一维，然后相当于是子集和，用高维前缀和即可。状态压缩，可以仔细思考。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e7 + 67;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
#define uint unsigned int
uint seed;
inline uint getnext(){
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}

bool _u;

int n;
uint b[N], ans;
bool ispri[N];

bool _v;

int main(){
	cerr << abs(&_u - &_v) << " MB\n";
	
	n = read(), seed = read();
	for(int i = 1; i <= n; ++i) b[i] = getnext();
	ispri[1] = 1;
	for(int i = 1; i <= n; ++i){
		if(!ispri[i])
			for(int j = i; j <= n; j += i)
				b[j] += b[j / i], ispri[j] = 1;
		ans ^= b[i];
	}
	printf("%lld\n", ans);
	return 0;
}

Ⅱ. [ARC100E] Or Plus Max

将题目转成对于每个 \(K\) 求 \(i | j = K\) 的最大值，然后就是求子集前缀最大值。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N = (1 << 19) + 67;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}

bool _u;

int n;
ll ans;
struct node{
	ll x, y;
	node operator + (const node &p){
		node z;
		if(x > p.x) z.x = x, z.y = max(y, p.x);
		else z.x = p.x, z.y = max(x, p.y);
		return z; 
	}
}a[N];

bool _v;

int main(){
	cerr << abs(&_u - &_v) / 1048576.0 << " MB\n";
	
	n = read();
	for(int i = 0; i < (1 << n); ++i) a[i].x = read(), a[i].y = -1e18;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < (1 << n); ++j)
			if(j & (1 << i)) a[j] = a[j] + a[j ^ (1 << i)];
	for(int i = 1; i < (1 << n); ++i){
		ans = max(ans, a[i].x + a[i].y);
		printf("%lld\n", ans);
	}
	return 0;
}

参考：https://zhuanlan.zhihu.com/p/651143987