mutable/term 设计

设计目标

可变的 TermPolynomial[A] 是分布形式多元多项式的容器，算法可以逐步更新它（添加一项、乘入一个因子、乘以一个单项式），同时它在每个可观察的时刻都保持 immut/term 的规范有序项数组。

数学背景

该容器持有某个 $f \in R[x_0, x_1, \dots]$ 的规范项列表：各项 $(\alpha_k, c_k)$ 在单项式序下满足 $\alpha_1 \succ \alpha_2 \succ \cdots$ ，且每个 $c_k \neq 0$ 。原地操作就是赋值：

\begin{aligned} \texttt{add\_term\_inplace}(\alpha, c) &: f \leftarrow f + c\,x^\alpha, \\ \texttt{add\_inplace}(g) &: f \leftarrow f + g, \\ \texttt{mul\_inplace}(g) &: f \leftarrow f g, \\ \texttt{scale\_inplace}(\gamma, c) &: f \leftarrow c\,x^\gamma f . \end{aligned}

设计决策

替换数组，从不部分编辑

每个修改方法都先计算出完整的规范数组，再将其赋给私有字段。读者永远看不到半排序或未合并的状态，别名也无害：在 p.add_inplace(p) 中，循环遍历旧数组而字段被重新赋值，得到 $2p$ ；p.mul_inplace(p) 在赋值前算出 $p^2$ 。

单项插入复用共享的规范化

add_term_inplace 将新项追加到数组副本上，并用不可变构造函数重新规范化， $O(m \log m)$ 。二分查找后再插入或合并可以做到 $O(m)$ （主要开销在移动数组），但会重复规范化逻辑。这里的选择是让两层共用同一个规范化例程。

add_inplace(g) 逐个插入 $g$ 的项，因此对 $g$ 中的 $n$ 个项，其代价为 $O(n\,(m + n)\log(m + n))$ ，而 +（复制后调用 add_inplace）继承了这一代价。这是与 immut/term 的主要性能差异，后者的 + 只在 $O((m+n)\log(m+n))$ 内规范化一次。对于大型求和，可以用 to_immut 转换后在那里相加再转换回来，或者构建项列表后调用一次 from_terms。

乘以单项式保持顺序

scale_inplace 将 $(\alpha, a) \mapsto (\alpha + \gamma, ac)$ 并丢弃为零的乘积，无需排序，理由与不可变类型相同：在单项式序下 $\alpha \mapsto \alpha + \gamma$ 严格递增，因此严格降序的数组仍保持严格降序（推导）。

乘积与幂委托实现

*、mul_inplace 和 pow 把两个操作数都转换为不可变类型，在那里相乘后再转换回来。每次转换代价为 $O(m \log m)$ ，相对于 $O(mn \log(mn))$ 的乘积很小，并且保证结果与不可变层相同。

正确性 / 不变量

每次公开调用之后都处于规范形式（严格降序、已合并、无零）；派生的 == 就是多项式相等。
与 immut 一致：对每个操作都有 from_immut(a).op(...).to_immut() == a.op(...)，并且原地操作使接收者等于对应运算符的结果。
隔离：copy、to_terms、coefficients、from_immut 和 to_immut 从不与接收者共享数组。
复杂度：add_term_inplace 为 $O(m \log m)$ ；add_inplace 和 + 为 $O(n(m+n)\log(m+n))$ ；mul_inplace 和 * 为 $O(mn\log(mn))$ ；scale_inplace 为 $O(m)$ 。

被否决的替代方案

惰性规范化（现在追加，读取时排序）：插入廉价，但每次查询都必须检查或恢复规范形式，且 == 会依赖隐藏状态。
用链表或树结构存放项：这正是 mutable/sparse 所提供的；项容器保持为扁平数组，以便快速有序遍历。

边界

不支持按指数查找系数；请使用 mutable/sparse。
add_inplace 没有针对大型操作数优化（见上文）。
变量按位置寻址；需要名字时请使用 mutable/context。
immut/term 所排除的一切，这里同样排除。