一些混沌 rprsq 想法

本文记录了模拟赛时对区间加区间求和的一些完全，完全，没有任何作用的思考。

就是区间加要比较快，区间求和要 $O(1)$，很容易想到值域分块对吧。

拿一种比较普遍（大概）的值域分块举例，维护一个 $ad_i$ 表示第 $i$ 块的加法标记，一个 $f_i$ 表示前 $i$ 块的前缀和，一个 $c_i$ 表示$i$ 所在块的左端点到 $i$ 的和，然后块长取 $\sqrt n$，你得到一个 $O(\sqrt n) - O(1)$ 的做法。

昨天睡的巨晚，今天一直在神游，然后甚至分析了一下这个值域分块的性质，你发现 $ad$ 上面永远做一堆区间加定值，$c$ 上面永远做一堆区间加等差数列，$f$ 是个递推，大概没法优化。

还没睡醒的我发现，区间加定值或者等差数列，是经典指令集。用指令集做这几个操作之后就只剩下了 $f$ 的递推，修改复杂度变为 $O(\dfrac{B}{w}+w+\dfrac{n}{B})$，其中 $w=8$，然后你得到了一个 $O(\sqrt{\dfrac{n}{w}})-O(1)$ 的做法，写了一下发现，比直接分块快了那么一丢丢，嗯，基本是个废物。

然后我想到，区间加定值或者等差数列，单点求值，这不是值域分块吗，所以可以套娃，套一层即可得到 $O(\sqrt B + \dfrac{n}{B})$ 的优秀复杂度，你得到一个 $O(n^{\frac{1}{3}})-O(1)$ 的做法。

把套娃套下去，说不定能套出类似 sqrt-tree 的东西，你会发现套出来一个复杂度 $T(n) = O\left(\dfrac{n}{B}\right) + T(B)$ 的东西，这显然取 $B = \dfrac{n}{2}$，然后我有一瞬间竟然觉得我得到了一个 $O(\log n) - O(1)$ 的做法，但是思考了 1s 之后发现，值域分块的查询居然是递归下去算的，所以你得到了一 棵 线 段 树，呕。

既然递归不太行那就直接计算，直接计算不久指令集嘛，所以你得到了线 段 树 维 护 区 间 指 令 集，呕。

意识到了自己今天有多啥比，然后回想一下分块套娃的本质，所以你得到了多 叉 线 段 树，呕。

然后我实在是太困了，写完这篇博客记录一下我的啥比经历就去睡觉了，白白。