自动搬运

查看原文

来自洛谷，原作者为

	迟暮天复明 #ee82ee

搬运于2025-08-24 22:57:41，当前版本为作者最后更新于2024-09-09 21:37:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前情提要

如果有人认为我写的比官方题解烂我直接反手撤下这篇题解。

前置知识：高维前缀和

你考虑假设我们直接高位前缀和维护了这个子集和，那么查询操作的确是 $O(1)$ 了，但是改完一个数之后就得重新 $O(2^N)$ 跑一遍高位前缀和，然后你就寄了。

所以考虑把两个操作平衡到都用 $O(2^{N/2})$ 时间。这说明我们查询操作的时候可以枚举 $2^{N/2}$ 个数，修改的时候只能修改 $2^{N/2}$ 个数。

考虑设 $F_S$ 表示前 $N/2$ 位和 $S$ 完全一致，后 $N/2$ 位是 $S$ 子集的所有数字之和。

那么对于查询操作，我们只需要对着 $X$ 的前 $N/2$ 位枚举子集，然后累加即可。

对于修改操作，因为 $X$ 的前 $N/2$ 位是钦定的，所以就相当于在他的后 $N/2$ 位上跑高维前缀和。

总时间复杂度 $O(Q2^{N/2})$，对时间限制的谴责，代码。