> 线段树不只是线段树
一、线段树的前提
线段树能够高效处理区间问题，要求所维护的聚合运算满足以下条件：
1. 结合律：保证左右子树信息可以任意顺序合并，树形结构有效；
2. 单位元：空区间返回单位元，使查询过程能正确处理不相交部分；
3. 分配律（仅当涉及区间修改时）：修改操作与聚合运算之间需要满足分配律，以便懒标记高效下传。
前两条性质构成代数结构中的幺半群。若仅进行查询操作，线段树维护的只需是一个幺半群；但若涉及区间修改，还要求修改操作与聚合运算之间存在类似分配律的同态性质，否则懒标记无法合并与下传。
二、实例：P1438 无聊的数列
题目要求支持两种操作：
* 区间 [l,r][l,r][l,r] 加上首项为 KKK、公差为 DDD 的等差数列；
* 单点查询第 ppp 个数的值。
直接维护的困难
对于一次操作，位置 j∈[l,r]j \in [l,r]j∈[l,r] 的增量为：
K+D(j−l)K + D(j-l) K+D(j−l)
多次操作叠加后，总增量为：
∑t[Kt+Dt(j−lt)]=∑tKt+∑tDt(j−lt)\sum_t \left[ K_t + D_t (j-l_t) \right] = \sum_t K_t + \sum_t D_t (j-l_t) t∑ [Kt +Dt (j−lt )]=t∑ Kt +t∑ Dt (j−lt )
问题出现在第二项 ∑tDt(j−lt)\sum_t D_t (j-l_t)∑t Dt (j−lt )。由于不同操作的左端点 ltl_tlt 不同，无法将 jjj 从求和符号中提出，导致下传标记时无法统一计算。
学习TJ思想
将原式展开：
∑tDt(j−lt)=j∑tDt−∑tDtlt\sum_t D_t (j-l_t) = j \sum_t D_t - \sum_t D_t l_t t∑ Dt (j−lt )=jt∑ Dt −t∑ Dt lt
代入总增量得：
(∑tKt−∑tDtlt)+j(∑tDt)\left( \sum_t K_t - \sum_t D_t l_t \right) + j \left( \sum_t D_t \right) (t∑ Kt −t∑ Dt lt )+j(t∑ Dt )
令
C=∑tKt−∑tDtlt,B=∑tDtC = \sum_t K_t - \sum_t D_t l_t,\quad B = \sum_t D_t C=t∑ Kt −t∑ Dt lt ,B=t∑ Dt
则增量可写为关于全局下标 jjj 的形式：
C+BjC + B j C+Bj
此时常数项 CCC 和一次项系数 BBB 都是可加量。线段树只需维护这两个懒标记即可支持区间加等差数列：
* 更新节点时，区间和增加 C⋅len+B⋅(L+R)⋅len2C \cdot \text{len} + B \cdot \dfrac{(L+R)\cdot \text{len}}{2}C⋅len+B⋅2(L+R)⋅len ；
* 下传标记时，将 CCC 和 BBB 分别加到左右孩子，并更新其区间和。
发现
重新观察：
∑tKt+∑tDt(j−lt)\sum_t K_t + \sum_t D_t (j-l_t) t∑ Kt +t∑ Dt (j−lt )
不难发现：之所以无法处理，就是因为该式子不满足分配律！
再观看正解的式子：
(∑tKt−∑tDtlt)+j(∑tDt)\left( \sum_t K_t - \sum_t D_t l_t \right) + j \left( \sum_t D_t \right) (t∑ Kt −t∑ Dt lt )+j(t∑ Dt )
不难发现：这刚好是一次函数，而一次函数是满足分配律的！
推广
显然的，只要将原式化成任意次函数的形式，就可以线段树维护。
三、总结
因此，线段树其实是维护任意次多项式的东西。
