高维前缀和
二维前缀和
一般的做法是容斥:
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[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];
三维前缀和
同上,有:
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
for (int k = 1; k <= n; ++ k)
a[i][j][k] += a[i - 1][j][k];
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
for (int k = 1; k <= n; ++ k)
a[i][j][k] += a[i][j - 1][k];
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
for (int k = 1; k <= n; ++ k)
a[i][j][k] += a[i][j][k - 1];
显然也可以拓展成 \(k\) 维。
SOSDP
要解决的是如下的问题:
对于所有的 \(i, (i \in [0, 2^n-1])\),求解 \(\sum_{j \subset i} a_j\)(或者类似于求子集某些信息)。
想法如下:
将 \(n\) 位的二进制理解为 \(n\) 维,每一维仅有两个值(0 / 1),上面说的子集其实也就是高维前缀和。
故考虑枚举当前在哪一维上做前缀和,对应做即可,时间复杂度 \(\mathcal O(n 2^n)\)。
for (int j = 0; j < n; ++ j)
for (int i = 0; i < 1 << n; ++ i)
if (i >> j & 1) f[i] += f[i ^ (1 << j)];
标签:前缀,int,如下,子集,一维,高维
From: https://www.cnblogs.com/chzhc-/p/18531285