不出意外应该是把最后一步冲过去了...感谢开学典礼(雾)
对于标题，如果信息可以 \Theta(1) 简单合并，那么存在 \Theta((n+q)\alpha(n)) 的做法.
-1 暴力
预处理所有区间的信息然后 \Theta(1) 询问，复杂度 \Theta(n^2)-\Theta(1).
0. 线段树上分治
建立线段树，对每个非叶节点 [l,r] 的划分点 mid，预处理该区间内以 mid 为结尾的所有后缀的信息和以 mid+1 开头的所有前缀的信息. 每个节点贡献复杂度 \Theta(len)，总复杂度 \Theta(n\log n). 对于询问，定位到该询问将要被拆分成两部分的区间，\Theta(1) 合并预处理的信息. 定位的过程相当于求 lca，那么可以用四毛子做到总复杂度 \Theta(n\log n)-\Theta(1)
0.5 Sqrt tree
虽然 lxl 把这个名字批判了一番，但先叫这个吧(
虽然和接下去的优化没有什么复杂度上的关联，但具有启发性(可能).
把区间按照 \sqrt n 分块，对于跨块的查询，我们使用 -1 中的方法处理块间的信息，并预处理每个块的前后缀信息，复杂度 \Theta(n)；对于块内的查询，递归下去进行. 那么子问题的规模每次会变成 \sqrt{n}，进行 \Theta(\log\log n) 次递归就会变为 \Theta(1)，复杂度 \Theta(n\log\log n).
定位同样在求lca，可以 O(1) 查询
1. ???
我愿称之为窦树(雾)
发现在 0.5 中块间信息并没有必要用 \Theta(n^2) 的做法去做，本质上还是一个规模为 \Theta(n/B) 的区间查询问题. 那么我们考虑按照 \log n 分块，对于跨块的询问，使用 0 的做法维护块间信息，块内的询问递归下去. 那么问题规模每次变为 \Theta(\log n)，最多 \Theta(\log^* n) 就会变成 \Theta(1)，那么树深度 \Theta(\log^* n)，总复杂度 n\log^* n+q.
???. ???
发现这个复杂度甚至可以迭代！设上一层数据结构的树深度为 T(m-1,n)，那么按照 T(m-1,n) 分块，块间信息用上一层数据结构维护，块内递归下去. 那么这一层数据结构的树深度就是每次把 n 变成 T(m-1,n) 直到 n=\Theta(1) 的次数.
稍微手玩一下可以发现，m=1 时就是 \log^* n，m=2 时就是对 n 不停取 \log^* 直到 n=\Theta(1) 的次数，以此类推. 这个东西的复杂度随 m 增大下降得非常快，我们找到最小的满足 T(m,n)=\Theta(1) 的 m，那么来计算此时的复杂度. 经过查表可以发现，m 就是反阿克曼函数 \alpha(n). 考虑询问复杂度，每次需要花费 \Theta(1) 时间进入上一层数据结构，那么询问复杂度 \Theta(\alpha(n)). 预处理时，第 m 层需要花费 \Theta(nT(m,n)) 的时空复杂度进入到规模为 \Theta(nT(m,n)/T(m-1,n)) 的下一层数据结构，因此预处理的时空复杂度为 \Theta(n\alpha(n))，总复杂度 \Theta((n+q)\alpha(n))
好像已经达到下界了？
下面是与之无关的一个东西，也是非常规分块的一个例子，是块介绍给我的. 除此之外，sqrt tree 也是块独立发现并介绍给我的. 由于块已经退役了，这成为了宝贵的文化遗产(雾).
使用区间加区间求和为例子. 考虑不使用 \sqrt n 分块而是先按 n^{2/3} 分块，分出的块称为大块，对每个大块再按 n^{1/3} 分块，分出的块称为小块. 这样形成一个三层的分治结构. 那么考虑一次提取区间，必然是形如 若干散点-若干小块-若干大块-若干小块-若干散点 的东西的一个部分，每个“若干”的数量为 O(n^{1/3}). 每个节点维护标记，下传需要 O(n^{1/3}) 的时间，每次修改只会涉及到 \Theta(1) 个节点下传标记，那么询问和修改的复杂度都为 n^{1/3} .
当然也可以把 3 换成别的东西，做到 O(xn^{1/x}). 到这里并没有什么用，但当查询和修改不平衡时，这个东西可以做到用 O(xn^{1/x}) 完成其中一个，用 O(x) 的复杂度完成另一个. 举例，如果有 O(n) 次单点修改 O(n\log n) 次区间求和，那么可以做到 O(nxn^{1/x}) 复杂度修改 O(xn\log n) 查询，解一下就得到 x=\log n/\log\log n，这时复杂度为 O(n\log^2 n/\log\log n).
upd 折腾了一番搞到了论文，大概看了一下发现确实是对的(虽然复杂度毛估估),也确实是下界.