这是我对 @璀璨星空1 讲课的笔记，也是 Fredman–Volper 的 dynamic partial match retrieval 算法。
TL；DR：我们可以在 $\mathcal O^{*}(1.2259^n(n+q)+2^n)$ 的时间复杂度内解决本题的加强版：支持在线对 $a$ 数组进行修改并回答本题的询问。注意到，这严格强于本题现有题解中的 $\mathcal O^{*}(1.2599^nq+2^n)$。按照 TCS 传统，我们忽略所有非指数因子。
首先让我们形式化的定义加强版问题：
你拥有一个长度为 $2^n$ 的权值数组 $w$，并需要在线的回答以下 $q$ 次询问，每个询问形如：
- 修改：给定一个位置 $p$ 和整数 $x$，将 $w_p\leftarrow w_p+x$。
- 查询：给定一个 $01$ 串 $S$，求 $w$ 数组中所有下标适配 $S$ 的位置的 $w_T$ 之和，其中，$T$ 适配 $S$ 当且仅当对于 $[1,n]$ 中每个位置 $i$，$S_i\in \{T_i,\text{'?'}\}$。
首先，我们可以把原问题转化为 $n$ 个这样的子问题：所有查询中的 $0/1$ 个数之和相同，不妨设其为 $sn$，其中 $s$ 是一个 $[0,1]$ 之间的实数。
我们尝试确定 $b\in [s,1]$ 且 $bn\in \Z$。并选出若干大小为 $bn$ 的集族 $\mathcal{B} \subseteq \binom{[n]}{bn}$。使得每个大小为 $sn$ 的集合 $A$ 都至少包含于一个 $B\in \mathcal B$。下面我们称集合 $A$ 为小集合，集合 $B$ 为大集合。
先忽略如何选出 $\mathcal B$ 的问题。假设我们已经选出了集合 $\mathcal B$，我们将对每个 $B\in \mathcal B$ 开一个大小为 $2^{bn}$ 的 map（经过精细的实现可以用数组代替，但为了方便我们暂且称之为 map），在这个 map 中记录：将 $B$ 中的每个数替换为 $0/1$，其它数保留为 $\text{?}$，如此所带来的权值和。举个例子，当 $n=5,B=\{1,2,4\}$ 时，我们会存储：
- $\text{00?0?}$
- $\text{00?1?}$
- $\text{01?0?}$
- $\text{01?1?}$
- $\text{10?0?}$
- $\text{10?1?}$
- $\text{11?0?}$
- $\text{11?1?}$
这些问题的答案。在修改时，每个 $B$ 中只有一个数会被修改，因此产生 $|\mathcal{B}|$ 的时间代价。
在查询时，不妨设其中的 $0/1$ 构成的集合为 $A$，我们找到某个 $B\in \mathcal{B}$ 使得 $A\subseteq B$，根据定义，一定存在这样的 $B$，我们枚举 $2^{(b-s)n}$ 中可能的替换求和即可得到答案，例如，若询问 $\text{01???}$，$A=\{1,2\}$，我们找到了 $B=\{1,2,4\}$ 包含他，只需对记录的这些求和：
- $\text{01?0?}$
- $\text{01?1?}$
不难发现我们希望 $\max(|\mathcal{B}|,2^{bn-sn})$ 尽可能小——当 $b$ 上升时，前者下降，而后者提高。因此我们希望二者尽可能相等。
不过，在分析渐进复杂度之前，我们先给出 $n=20$ 时每个 $s$ 所对应的最优 $|\mathcal B|$、$2^{bn-sn}$ 和代价，也就是 $\max(|\mathcal{B}|,2^{bn-sn})$。$\mathcal B$ 采用简单的贪心算法生成。
| $s$ | $b$ | 修改 $\lvert\mathcal B\rvert$ | 查询 $2^{(b-s)n}$ | cost |
|---|---|---|---|---|
| 0.00 | 0.00 | 1 | 1 | 1 |
| 0.05 | 0.15 | 7 | 4 | 7 |
| 0.10 | 0.30 | 18 | 16 | 18 |
| 0.15 | 0.40 | 37 | 32 | 37 |
| 0.20 | 0.50 | 58 | 64 | 64 |
| 0.25 | 0.55 | 98 | 64 | 98 |
| 0.30 | 0.65 | 81 | 128 | 128 |
| 0.35 | 0.70 | 90 | 128 | 128 |
| 0.40 | 0.75 | 85 | 128 | 128 |
| 0.45 | 0.80 | 67 | 128 | 128 |
| 0.50 | 0.80 | 103 | 64 | 103 |
| 0.55 | 0.85 | 63 | 64 | 64 |
| 0.60 | 0.90 | 22 | 64 | 64 |
| 0.65 | 0.90 | 26 | 32 | 32 |
| 0.70 | 0.90 | 30 | 16 | 30 |
| 0.75 | 0.95 | 16 | 16 | 16 |
| 0.80 | 1.00 | 1 | 16 | 16 |
| 0.85 | 1.00 | 1 | 8 | 8 |
| 0.90 | 1.00 | 1 | 4 | 4 |
| 0.95 | 1.00 | 1 | 2 | 2 |
| 1.00 | 1.00 | 1 | 1 | 1 |
在使用互联网上能够搜索到的最好覆盖后（），新的表格如下（参考了 https://coveringrepository.com）：
| $s$ | $b$ | 已知 $\lvert\mathcal B\rvert$ | 查询 $2^{(b-s)n}$ | 总代价 |
|---|---|---|---|---|
| 0.00 | 0.00 | 1 | 1 | 1 |
| 0.05 | 0.15 | 7 | 4 | 7 |
| 0.10 | 0.30 | 16 | 16 | 16 |
| 0.15 | 0.40 | 28 | 32 | 32 |
| 0.20 | 0.45 | 63 | 32 | 63 |
| 0.25 | 0.55 | 64 | 64 | 64 |
| 0.30 | 0.60 | 84 | 64 | 84 |
| 0.35 | 0.65 | 121 | 64 | 121 |
| 0.40 | 0.70 | 119 | 64 | 119 |
| 0.45 | 0.75 | 100 | 64 | 100 |
| 0.50 | 0.80 | 64 | 64 | 64 |
| 0.55 | 0.85 | 40 | 64 | 64 |
| 0.60 | 0.85 | 59 | 32 | 59 |
| 0.65 | 0.90 | 24 | 32 | 32 |
| 0.70 | 0.90 | 30 | 16 | 30 |
| 0.75 | 0.95 | 16 | 16 | 16 |
| 0.80 | 1.00 | 1 | 16 | 16 |
| 0.85 | 1.00 | 1 | 8 | 8 |
| 0.90 | 1.00 | 1 | 4 | 4 |
| 0.95 | 1.00 | 1 | 2 | 2 |
| 1.00 | 1.00 | 1 | 1 | 1 |
接下来就是渐进复杂度部分了。
首先，$|\mathcal B|$ 具有显然的下界：$R=\frac{\binom{n}{sn}}{\binom{bn}{sn}}$
上界方面，我们随机选取一个集合 $B$，对于固定的 $A$，被包含的概率也就是 $\frac{1}{R}$，现在我们选 $NR$ 个 $B$，固定的 $A$ 未被覆盖的概率也就是 $e^{-N}$，而总共只有 $2^n$ 个 $A$，union bound 一下，我们选择 $N=2n$ 之类的就肯定让所有 $A$ 都被覆盖的概率大于 $0$ 了！故一定存在这样的方法。这就说明 $|\mathcal{B}|=\mathcal O^{*}(R)$。
定义 $H(x)=1-x\log_2 x-(1-x)\log_2(1-x)$，$R=2^{(H(s)-bH(s/b))n+\mathcal O(\log n)}$。于是两边取等，数值分析出最差点在 $s=0.3531,b=0.6469$，代价是 $\mathcal O^{*}(1.2259^n)$。
在 OI 实现方面，显然我们不可能放任最开始的那个 $n$ 不管，一个好方法是二分答案代价，并计算出对应的 $|\mathcal B|$。总之感觉应该是可实现的。
参考文献：M. L. Fredman, D. J. Volper. The Complexity of Partial Match Retrieval in a Dynamic Setting. Journal of Algorithms, 3(1):68–78, 1982.