官方题解只能做到 $O(nM \log n + qM\log^2 n)$？玩的太差了。这题可以把普通“FWT + 树链剖分”做法的单次修改降到最坏 $O(M\log n)$，预处理做到 $O(nM)$。询问也不必每次执行完整逆 FWT：单个询问只需 $O(M)$，连续询问还可以共享计算，进一步降低总复杂度。官方题解给出的满分做法保留了修改中的 $\log^2 n$，以及预处理和询问中的 $\log M$ 因子。([QOJ][1])
以下令 $M$ 为不小于 $m$ 的最小二次幂，全部运算均在模 $p=10007$ 的意义下进行。题目要求维护所有非空连通子树的点权异或和分布，支持单点修改；数据满足 $n,q\le 30000$，$M\le128$，修改次数不超过 $10000$。([QOJ][2])
一、直接在异或字符下做树形 DP
对每个 $s\in[0,M)$，定义 $\chi_s(x)=(-1)^{\operatorname{popcount}(s\operatorname{\&}x)}$。它最重要的性质是 $\chi_s(x\oplus y)=\chi_s(x)\chi_s(y)$，因此，连通子树的异或和经过这个映射后，就变成了各个结点贡献的乘积。
任意选根。定义 $F_u(s)$ 为：在 $u$ 的子树中，所有包含 $u$ 的连通点集的字符值之和。一个这样的点集，对于每个儿子 $v$，要么不进入 $v$ 的子树，要么选择一个包含 $v$ 的连通点集，所以有
$$ F_u(s)=\chi_s(v_u)\prod_{v\text{ 是 }u\text{ 的儿子}}\bigl(1+F_v(s)\bigr). $$
每个非空连通点集都有唯一的深度最小结点，故整个答案分布在字符 $s$ 下的值为 $H(s)=\sum_u F_u(s)$。
这里虽然等价于在 FWT 域中计算，但不需要对每个结点执行一次 FWT。单点权值的变换结果就是 $\chi_s(v_u)\in{1,-1}$，直接计算全部 $M$ 个坐标即可。每条树边、每个坐标只进行常数次运算，因此静态 DP 的复杂度是 $O(nM)$，没有额外的 $\log M$。
接下来固定一个坐标 $s$，暂时省略公式中的 $s$。不同坐标完全独立，最后把维护成本乘上 $M$ 即可。
二、用加权平衡树消掉第二个 $\log n$
记 $h_u$ 为 $u$ 的重儿子，也就是子树最大的儿子。把轻儿子的贡献合并为 $a_u=\chi_s(v_u)\prod_{v\text{ 是 }u\text{ 的轻儿子}}(1+F_v)$，则原转移变成 $F_u=a_u(1+F_{h_u})$；没有重儿子时取 $F_{h_u}=0$。
考虑一条从上到下依次为 $u_1,u_2,\ldots,u_\ell$ 的重链。不断展开转移，得到 $F_{u_i}=\sum_{j=i}^{\ell}\prod_{t=i}^{j}a_{u_t}$。
这就把树形 DP 化成了一个序列问题：链顶的 $F$ 是这条链所有非空前缀的乘积之和，而整条链上各个 $F$ 的总和，是所有非空子区间的乘积之和。
于是，对链上的一个区间维护四个量：$P$ 为整段乘积，$L$ 为所有非空前缀的乘积之和，$R$ 为所有非空后缀的乘积之和，$S$ 为所有非空子区间的乘积之和。
合并相邻区间 $A,B$ 时，整段乘积为 $P=P_AP_B$；前缀要么完全位于 $A$，要么包含整个 $A$，所以 $L=L_A+P_AL_B$；同理，$R=R_B+P_BR_A$。跨越分界点的子区间唯一对应于一个 $A$ 的非空后缀和一个 $B$ 的非空前缀，因此 $S=S_A+S_B+R_AL_B$。
单点 $a_u$ 的信息是 $(a_u,a_u,a_u,a_u)$，空区间的信息是 $(1,0,0,0)$。每次合并只需要常数次标量运算。
如果在每条重链上建立普通平衡树，一次修改经过 $O(\log n)$ 条重链，每条链内部又需要 $O(\log n)$，仍然只能得到 $O(M\log^2 n)$。关键是：平衡树不能按结点个数平衡，而应该按下面的权重平衡。
记 $\operatorname{sz}(u)$ 为原树子树大小，定义 $w_u=\operatorname{sz}(u)-\operatorname{sz}(h_u)=1+\sum_{v\text{ 是轻儿子}}\operatorname{sz}(v)$。对于链顶为 $t$ 的重链，整条链的 $w$ 之和恰好等于 $\operatorname{sz}(t)$。
在每条链上建立一棵保持原有顺序的二叉搜索树，每个搜索树结点对应一个原树结点。递归建树时，选择加权中位数作为根，使左右两侧的权重和都不超过当前总权重的一半。搜索树结点的信息由“左子树区间、当前单点、右子树区间”依次合并得到。
设某条链的总权重为 $W$，其中结点 $u$ 的权重为 $w_u$。每向下一层，当前区间总权重至少减半，而包含 $u$ 的区间总权重不能小于 $w_u$，所以 $u$ 到这棵平衡树根的路径长度为 $O(1+\log(W/w_u))$。
现在分析一次修改。设依次经过的重链链顶为 $t_0,t_1,\ldots,t_r$，在这些链上需要修改的结点依次为 $x_0,x_1,\ldots,x_r$，其中 $x_0$ 是原修改点，$x_{i+1}=\operatorname{parent}(t_i)$。记 $S_i=\operatorname{sz}(t_i)$，$W_i=w_{x_i}$。
因为 $t_i$ 是 $x_{i+1}$ 的轻儿子，所以 $W_{i+1}\ge S_i$。于是各条链内部的路径长度可以望远镜求和：
$$ \sum_{i=0}^{r}\left(1+\log\frac{S_i}{W_i}\right) \le (r+1)+\log\frac{S_r}{W_0} \le (r+1)+\log n =O(\log n). $$
最后一步使用了轻边数量为 $O(\log n)$。因此，一次修改在所有重链内部合计只访问 $O(\log n)$ 个平衡树结点，而不是每条链各访问 $O(\log n)$ 个。乘上坐标数，得到最坏 $O(M\log n)$；这里不需要依赖 Splay 的均摊分析。
还需要解决轻儿子贡献的更新。不能简单地“除掉旧的 $1+F_v$，乘上新的 $1+F_v$”，因为这个因子可能在模 $p$ 意义下为零。对每个 $u,s$，维护零因子的个数 $z_u$，以及包含结点自身字符值的非零部分乘积 $b_u=\chi_s(v_u)\prod_{v\text{ 是轻儿子},,1+F_v\ne0}(1+F_v)$。实际使用的 $a_u$ 在 $z_u=0$ 时等于 $b_u$，否则等于零。
删除或加入轻儿子的贡献时，零因子只修改计数，非零因子使用乘法和逆元。由于模数 $10007$ 固定且为质数，可以预处理所有非零剩余的逆元，使每个坐标的更新都是 $O(1)$。
具体修改流程也就很直接了。先修改原结点的字符贡献，然后沿加权平衡树向上重新计算。处理一条链之前，记录其旧的 $L,S$；更新之后，把全局 $H$ 加上 $S_{\mathrm{new}}-S_{\mathrm{old}}$，再使用链顶 $F$ 的变化，也就是 $L_{\mathrm{old}}$ 到 $L_{\mathrm{new}}$ 的变化，更新链顶父亲的轻儿子乘积，继续处理上一条链。
若某个坐标的链顶 $L$ 没有变化，就不必继续向上传播这个坐标；即使该链的 $S$ 发生变化，也已经计入了全局 $H$。
修改点权时还有一个常数优化。设新旧点权的异或为 $\Delta$，则仅当 $\operatorname{popcount}(s\mathbin{\&}\Delta)$ 为奇数时，$b_u(s)$ 才需要取相反数。非零 $\Delta$ 恰好影响一半坐标。即使当前 $z_u(s)>0$，也必须更新这个被零因子遮住的 $b_u(s)$，否则以后零因子消失时会出错。
最后说明如何严格保证线性建树。先计算每条链的权重前缀和。定位加权中位数时，从区间两端分别做倍增探测，再在找到的候选区间内二分。若中位数左右分别有 $a,b$ 个结点，定位成本为 $O(1+\log(\min(a,b)+1))$。这个成本对一棵二叉树的所有结点求和为线性，可由递归式归纳证明。因此辅助结构的构造是 $O(n)$，初始 DP 和全部结点信息的计算都是 $O(nM)$，总预处理确实是 $O(nM)$。
三、询问使用按需逆变换
维护出 $H(s)$ 后，答案为 $\operatorname{Ans}(k)=M^{-1}\sum_{s=0}^{M-1}\chi_s(k)H(s)$。
这个等式可以直接用字符正交性证明：当 $x\ne0$ 时，选择 $x$ 的一个置位，把 $s$ 与翻转该位后的 $s$ 配对，$\chi_s(x)$ 两两抵消；而 $x=0$ 时，所有字符值都是 $1$，总和为 $M$。
所以，只查询一个 $k$ 时，直接计算上面的内积即可，复杂度是 $O(M)$，不需要 $O(M\log M)$ 的完整逆变换。
但还可以继续优化。若两次修改之间有很多询问，逐个计算内积会重复工作；直接做完整逆变换，又会为没有询问到的答案付费。可以使用一个在线的、按需展开的逆变换，同时兼顾这两种情况。
假设当前需要处理的变换数组为 $B$，长度为 $L$。根据目标下标当前最高位是 $0$ 还是 $1$，分别构造两个长度为 $L/2$ 的数组：$B^{(0)}*i=B_i+B*{i+L/2}$，$B^{(1)}*i=B_i-B*{i+L/2}$。随后查询只需要进入对应的那一半，并处理下一位。
因此可以把逆变换看成一棵二叉树。某个结点第一次被询问经过时，才执行这一层的蝶形运算，生成它的两个儿子；以后再次经过，就复用已有结果。到达叶子后乘上 $M^{-1}$，得到对应答案。已经回答过的 $k$ 直接缓存，重复询问只需 $O(1)$。
两个儿子的数组可以直接覆盖父亲数组的前后两半，因此只需要一个长度为 $M$ 的工作数组，以及 $O(M)$ 个展开标记。修改后将缓存标为失效，在下一次询问时重新从 $H$ 初始化即可，不必在没有询问时做任何逆变换。
设同一状态下询问了 $D$ 个不同的 $k$。在深度 $d$，最多展开 $\min(2^d,D)$ 个结点，每个结点的计算量为 $O(M/2^d)$。前约 $\log D$ 层每层总计算量至多 $O(M)$，后面的计算量按几何级数下降，所以总成本为 $O(M\log(D+1))$。
这意味着，只查询一个答案时是 $O(M)$；查询全部答案时是 $O(M\log M)$；查询部分答案时，则只支付 $O(M\log(D+1))$，而且不需要预先知道后续会询问哪些下标。
设修改次数为 $U$，询问次数为 $Q$，按修改划分出的各个区段中，不同询问参数的个数分别为 $D_b$。最终总时间复杂度为
$$ O\left( nM+UM\log(n+1)+Q+M\sum_b\log(D_b+1) \right), $$
空间复杂度为 $O(nM)$。其中单次修改是最坏 $O(M\log(n+1))$，单次未缓存询问至多 $O(M)$。
因为 $D_b\le M$，一个更简洁的总上界是 $O(nM+UM\log(n+1)+(U+1)M\log(M+1)+Q)$。当 $M\le n$ 时，这进一步简化为 $O(nM+UM\log(n+1)+Q)$；而上面的按区段表达式，在询问较少时还会更小。
这个做法的关键不只是把异或卷积变成逐点乘法，而是让重链内部的访问成本与轻边跨越时的子树规模变化相抵消，从而真正去掉修改中的第二个 $\log n$；再通过按需逆变换，避免在询问阶段重新引入不必要的工作。