FenWick Tree

Neutralized · 2022-08-28 20:48:27 · 个人记录

\text{FWT}

关于 Zeta Transform：套娃。

• Or：

如果能构造 F(a)_i \times F(b)_i = F(c)_i 并且可以从 F(x) \to x，那么可以快速计算这个值
考虑 zeta 变换，也就是子集和，容易发现 \zeta(a)_i \times \zeta(b)_i=\zeta(c)_i，这是因为 \sum_{j \subseteq i}a_j \times \sum_{k \subseteq i}b_k = \sum_{q \subseteq i}\sum_{j \bigcup k=q}a_jb_k= \zeta(c)_i。

那么就可以在 O(n2^n) 解决了。

注意快速 zeta 变换是可以求逆的，也就是说反号后可以做到 \zeta(x) \to x。所以真的做完了。

• And：

考虑做超集前缀和，那么这个也做完了。
具体来讲就是把 zeta 变换里 zeta[j^bit] -> zeta[j] 的部分反向即可。

• Xor：

其实这个 Xor 就和子集前缀和没关系了，所以可以把 zeta 先扔了（（
too young too naive，你推出来的任何分治式子都可以用 zeta 变换进行计算，复杂度完全一样。（至少模板题可以）

考虑妙妙构造，依然寻找那个 F(x)，由于我们的 F(x)_i 构造过程 应当尽量 只使用加减法，所以先假定和原序列所有项 线性相关，也就是可以表示成原序列每一项的加权和：

其中 fac(x,i) 表示考虑序列 x，它的第 i 项对应的权序列。
那么我们需要使得

由于 C_i=\sum_{j \oplus k=i}A_jB_k，带入后可以得到

为了便于处理，我们需要找到一种 fac 使得它与序列无关，只留下 fac(i)_{j} 的形式，并且需要满足 fac(i)_{j \oplus k}=fac(i)_jfac(i)_k
考虑两个数 i,j 的什么属性在 \operatorname{XOR} 之后是 i,j 原属性相乘，我们不妨设 fac(i)_j=(-1)^{|i \bigcap j|}，为什么呢，因为我们很智慧，一下子就看出这个东西满足以上需求和性质（（（
嗯并不知道为什么选了这个东西，但是它是有效的。

现在考虑转移，一定要注意过程中 不需要 考虑 zeta[j^bit]（不取）和 zeta[j]（取）现在分别是什么符号，因为这里的 +,- 符号 事实上表示 \times 1 或 \times (-1)，也就是是否取反。

钦定以下陈述中，\& 左边的为转移对象，右边的为转移量。（也就是考虑右边对左边贡献）
1.(j \oplus bit) \& j = (j \oplus bit) 不变，j \to^{+}(j \oplus bit)

2.j \& (j \oplus bit) = (j \oplus bit) 减少一位，需要对贡献取反，(j \oplus bit) \to^{-}j
3.(j \oplus bit) \& (j \oplus bit) =(j \oplus bit) 不变，保留贡献
4.j \& j = j 不变，保留贡献

最后因为 (j \oplus bit) \to j 增加一位，新的 \zeta_j 应当取反，所以转移式如下：