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