mutable/sparse 设计

设计目标

可变的 SparsePolynomial[A] 是本库的累加器：一种以对数时间逐项吸收项的多元多项式，适用于增量生成项的算法（展开乘积、收集贡献、从数据构建多项式）。

数学背景

该容器持有多项式 $f$ 的部分映射 $\operatorname{supp} f \to R \setminus \{0\}$ ， $\alpha \mapsto f_\alpha$ （见 immut/sparse 设计）。添加一个项就是对该映射的逐点更新：

(f + c\,x^\alpha)_\beta = \begin{cases} f_\alpha + c & \beta = \alpha, \\ f_\beta & \beta \neq \alpha, \end{cases}

因此只有键 $\alpha$ 发生变化，并且恰好在 $f_\alpha + c = 0$ 时离开支撑集。

设计决策

在树上逐点更新

选择。 set_coefficient 和 add_term_inplace 直接在 AVL 树上实现上述公式：一次查找，然后一次插入、更新或删除，每步 $O(\log m)$ 次比较。“没有零值”这一不变量在局部维护：set_coefficient(α, 0) 删除该键，add_term_inplace 在和变为零时删除该键，并忽略为零的增量。add_inplace(g) 是 $n$ 次这样的更新， $O(n \log(m + n))$ ，这正是在累加场景中选择此容器而非 mutable/term 的理由。

原地更新值也使 p.add_inplace(p) 具有良定义：迭代对每个键只访问一次，且只改写正在访问的键的值，从而得到 $2p$ 。

整体多项式操作委托实现

*、mul_inplace、pow 和 to_immut 都经由不可变类型实现，mul_inplace 和 scale_inplace 会先完整计算出结果，再清空并重新填充树。因此结果在构造上就与 immut/sparse 一致，且 p.mul_inplace(p) 得到 p 的平方。

复制即重建

copy 通过 from_terms 从项列表重建一棵新树， $O(m \log m)$ 。这要求系数满足 Eq + AddMonoid，因此对该类型而言，Copyable 和 MutablePolynomial 组合都带有这一约束；而稠密容器和项容器的 copy 是无约束的数组复制。

与其他多元容器的代价比较

操作	`immut/sparse`	`mutable/term`	`mutable/sparse`
添加一个项	$O(m \log m)$	$O(m \log m)$	$O(\log m)$
添加 $n$ 个项	$O((m+n)\log(m+n))$	$O(n(m+n)\log(m+n))$	$O(n \log(m+n))$
设置一个系数	重建	不可用	$O(\log m)$
系数查找	$O(\log m)$	$O(m)$	$O(\log m)$

正确性 / 不变量

没有零值；键是规范的。 每个修改方法都维护这一点；==（比较升序项列表）就是多项式相等。
与 immut 一致：from_immut(a).op(...).to_immut() == a.op(...)，并且原地操作使接收者等于对应运算符的结果。
隔离：copy、to_terms、from_immut 和 to_immut 都构建新的存储。
别名：对自身执行 add_inplace(p) 得到 $2p$ ；对自身执行 mul_inplace(p) 得到 $p^2$ 。

被否决的替代方案

哈希映射。 更新期望为 $O(1)$ ，但无序：相等和打印需要排序，且迭代顺序会与不可变类型不同。
允许零值并在读取时过滤。 更新更简单，但 size、is_zero 和 == 都需要跳过零。

边界

copy 是 $O(m \log m)$ ，而不是常数时间的快照。
不先物化 to_terms() 就无法从首项开始向下有序遍历。
变量按位置寻址；需要名字时请使用 mutable/context。
immut/sparse 所排除的一切，这里同样排除。