高维前缀和

理解

建议阅读博客

然后首先从二维前缀和理解

先从一维开始逐行进行前缀和

再从二维开始对一维的前缀和进行前缀和

多维是同理

一般多维前缀和在OI的应用为位运算的子集问题

例如求：$f_i = \sum_{j\in i} f_j $

即求 \(i\) 在二进制下的每一个子集的和

把二进制下每一位看成一个维度，然后每个维度值域为[0,1]

0涵盖0，1涵盖1和0，很像一个前缀和的形式

所以就是高维前缀和

代码：（这次没时间写了，先贺了一份）

// N 是位数
// a[0...2^N-1] 是初始数组
// dp[mask] 最终存储 s[mask]// 初始化 dp = a
for (int mask = 0; mask < (1 << N); ++mask) {dp[mask] = a[mask];
}// 按维度进行前缀和
for (int i = 0; i < N; ++i) { // 枚举维度 i (第 i 位)for (int mask = 0; mask < (1 << N); ++mask) {// 只对第 i 位是 1 的 mask 进行更新if (mask & (1 << i)) {// dp[mask] 的值，是从它第 i 位为 0 的那个状态转移过来的// 也就是 dp[mask] = dp[mask] + dp[mask 异或 (1<<i)]dp[mask] += dp[mask ^ (1 << i)];}}
}

例题

CF165E

CF1234F

旋转操作，