[GDOI2016] 疯狂动物城
对于大多树上区间问题往往加个树剖就能变成普通区间问题，只是说复杂度会加个 \(log\)，出题人这么做的理由可能是想锻炼一下评测姬吧选手的码力吧。而强制在线只需要可持久化数据结构即可。
本题同理可视作区间问题用线段树维护，考虑推式子降次以便于维护
\(ans=\sum_{i=1}^n\sum_{j=1}^{i-1}a_ij=\sum_{i=1}^na_i\frac{(i-1)i}{2}\)
本题信息较多考虑套用双半群模型，则只需考虑信息之间的合并，标记与信息合并，标记之间的合并，由于本题得可持久化，并且原题卡空间，所以得标记永久化，则不需要考虑标记群之间的合并。
先考虑如何将两个区间信息中的答案（记为 \(ans\) ）进行合并，显然对于靠左的区间贡献不变，可以考虑计算右边的区间贡献的变化量。
\[\begin{aligned} d&=\left[\sum_{i=l}^ra_i\frac{(i-1)i}{2}\right]-\left[\sum_{i=l}^{r}a_i\frac{(i-l)(i-l+1 )}{2}\right] \\ &=\sum_{i=l}^ra_i\frac{2il-2i-l^2+l}{2} \\ &=\frac{-l^2+l}{2}\sum_{i=l}^ra_i+(l-1)\sum_{i=l}^ra_ii \\ &=\frac{-l^2+l}{2}\sum_{i=l}^ra_i+(l-1)\left[(l-1)\sum_{i=l}^ra_i+ \sum_{i=l}^ra(i-l+1)\right] \\ &=\left[\frac{-l^2+l}{2}+(l-1)^2\right]\sum_{i=l}^ra_i+(l-1) \sum_{i=l}^ra(i-l+1) \end{aligned}\]对于第一项显然只需要维护区间和即可（记为 \(s1\) ），对于第二项则需要维护每一位乘上区间位置的和（记为 \(s2\) ）。这些东西在线段树上显然是好合并的。
\(s1\) 为左右区间 \(s1\) 之和。
\(s2\) 为左右区间 \(s2\) 之和再加上右区间的 \(s1\) 乘上左区间长度。
再考虑标记与信息的合并，本题只有简单的区间加操作，并且信息具有结合律，可以直接标记永久化所以只需要考虑 \(ans\)，\(s1\) 和 \(s2\) 的变化就行了。记 \(t\) 为本层完全覆盖的区间加的值之和，\(len\) 为本次查询的区间在本层的长度。
简单推导得到
\(ans\) 应加上 \(t\sum_{i=1}^{len}\frac{(i-1)i}{2}\)，可以预处理求和部分，也可以平方和。
\(s1\) 应加上 \(tlen\)
\(s2\) 应加上 \(t\frac{(len+1)len}{2}\)
虽然到这里线段树的讨论就结束了，但是由于不确定起点在哪边，上述东西正反都得做 ...
总结一下，线段树上信息需维护 \(ans,s1,s2\) 的正反情况（把 \(len\) 加入会更好写一点，不过空间常数会变大），标记只需维护 \(t\) 即可。
然后加上树剖、可持久化本题就结束了。
时空复杂度皆为 \(O(nlog^2n)\)。
优化可以考虑每个给每条链单独建一颗线段树，这样时空常数都会减小不少。
标签：frac,报告,题解,sum,ra,s2,区间,数据结构,s1 From： https://www.cnblogs.com/07Qyun/p/18456509