对于可以O(1)合并的具有结合律的信息，可以使用vEB树，每个节点处理前缀和后缀信息。对于在一棵树上查询的区间，要么完全被某个子树完全包含，要么可以拆成一个子树的后缀、一个所有子树的vEB树上的可空的区间，以及另一个子树的前缀。空间复杂度O(nloglogn)，预处理时间复杂度O(nloglogn)，查询复杂度O(loglogn)。不过没啥用，应该跑不过高效实现的复杂度较高的方法。

好像挺显然的，不知道有没有人讲过。

UPD：经过讨论发现可以按logn大小进行k层分块。设$\log^{(m)}$表示连续取m次log，若每层都采用O(nlogn)-(1)维护块，则可以做到$O(n)$-$O(\log^{(k)}n)$，且对于随机询问期望O(1)。k=1时应该相当有实用价值。

多层线段树应该是类似的。