$O(n\log^*n)$（<-记 $\log^*n$ 表示 $n$ 最多能连续取几次 $\log$） 预处理然后 $O(1)$ 查询，但在 OI 里没啥意义，本文不作讨论。

空间复杂度同预处理复杂度。

不知道现在 OI 界是否有同样的算法，如果没有的话，可以称之为三叶虫树（UTT），有的话麻烦评论区告知，会删掉这个命名。

UPD：由于评论区已被神仙告知有，命名删除。不过博主还是不知道其结构是否相同（感觉不太是？），所以还是挂在这里吧。求轻喷。

接着是算法。

观察 zkw 线段树区间查询的查询结构，以 RMQ 为例：

  for (l += M - 1, r += M + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
    if (~l & 1) ret = max(ret, zkw[l ^ 1]);
    if (r & 1) ret = max(ret, zkw[r ^ 1]);
  }

发现就是两边链查询，查询的信息类似于一条链上所有左/右儿子的兄弟们的最大值。

然后我们就只需要解决从叶子开始的链查询问题了，用一个 pair 维护这两个信息，然后甚至连原线段树都能省了。

我们观察到，如果预处理出每一种这样的链的答案，那查询就能做常数时间，但是预处理复杂度是 $O(n\log n)$ 的。

之所以造成这样的复杂度是因为出现了一堆所谓“冗余”信息，因为很容易发现不同节点的前缀和路径中会出现巨量重叠.

那我们如果把重叠的部分选择性记录下来不就可以省时间了？

于是我们给线段树分层以记录重叠信息。

然后，观察三叶虫的结构（？）：

很容易发现无论是横向还是纵向都被分成了三部分，于是我们采用仿生技术（？），把线段树也分成三部分。

画个图：

在每一部分内做从叶子开始的“前缀和”（<-其实是前缀操作，这里就以和为例，姑且称作前缀和了）。

比如说这个线段树的这个分法，所有会被计算的前缀和（就以和为例到底了吧）：

最底下一层：

16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31

中间那层：

8,9,10,11,12,13,14,15,8+4,9+4,10+5,11+5,12+6,13+6.14+7,15+7

最顶上一层：

2,3,2+1,3+1

对就是这样。

然后查询显然还是常数时间。

至于怎么分这棵树，有两种处理方法：直接数学推决策，或者干脆先花 $O(\log^2 n)$ 的时间枚举两条线然后看何时最优。

然后 OI 用的场景，数据范围绝大部分情况下不会超过 $2^{28}\approx2.68\times10^8$ 对吧，这个场景下预处理复杂度可以视作线性（枚举一下就会发现常数差不多 $3$ 左右）。空间复杂度同预处理复杂度。

如果真的有什么毒瘤到数据范围出得比这还大的出题人，那也没事反正常数还是很小（误），我们就要升级一下我们的三叶虫树了，把它变成四叶虫树（真）。

真就把分三层改成分四层就好了。这玩意的查询显然还是常数时间，预处理的常数当序列长度不到 $2^{2059}$ 时常数严控于 $3$。空间复杂度依然同预处理复杂度。

不可能真的有出题人出再大的数据范围了，不可能了。

真的要再大的话，复杂度开头给了。此时无非就是多分几层，然后再加一个层间前缀和（不用管这是什么）把查询稳在常数时间。空间复杂度还是同预处理复杂度。

例题：第一行输入序列长度和查询数，接着一行输入序列，接着若干行每行一个查询区间，所有输入为 $10^5$ 以内的正整数。

代码（分三层+枚举决策版）：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 9, Mx = 1 << 17;
int n, m, M = 1, h, lg[Mx << 1], x, y;
pii val[Mx << 1];
pii* suf[Mx << 1];
pii pmax(const pii& a, const pii& b) {
  return make_pair(max(a.first, b.first), max(a.second, b.second));
}
pii qlink(int pos, int len) {
  if (h - y > len) return suf[pos][len];
  pii ret = suf[pos][h - y - 1];
  len -= h - y, pos >>= h - y;
  if (y - x > len) return pmax(ret, suf[pos][len]);
  ret = pmax(ret, suf[pos][y - x - 1]);
  len -= y - x, pos >>= y - x;
  return pmax(ret, suf[pos][len]);
}
int main() {
  scanf("%d%d", &n, &m);
  while (M <= n || h <= 1) M <<= 1, ++h;
  for (int i = M + 1, a; i <= M + n; ++i) {
    scanf("%d", &a);
    ((i & 1) ? val[i ^ 1].first : val[i ^ 1].second) = a;
  }
  for (int i = M - 1; i > 1; --i)
    ((i & 1) ? val[i ^ 1].first : val[i ^ 1].second) =
        max(val[i << 1].first, val[i << 1 | 1].second);
  for (int x = 0, mx = INT_MAX; x < h; ++x)
    for (int y = x + 1; y < h; ++y) {
      int tmp = (x << x) + ((y - x) << y) + ((h - y) << h);
      if (tmp < mx) mx = tmp, ::x = x, ::y = y;
    }
  for (int i = (1 << x); i < (1 << (x + 1)); ++i) {
    suf[i] = new pii[x];
    suf[i][0] = val[i];
    for (int j = 1; j < x; ++j) suf[i][j] = pmax(suf[i][j - 1], val[i >> j]);
  }
  for (int i = (1 << y); i < (1 << (y + 1)); ++i) {
    suf[i] = new pii[y - x];
    suf[i][0] = val[i];
    for (int j = 1; j < y - x; ++j)
      suf[i][j] = pmax(suf[i][j - 1], val[i >> j]);
  }
  for (int i = M; i < M + M; ++i) {
    suf[i] = new pii[h - y];
    suf[i][0] = val[i];
    for (int j = 1; j < h - y; ++j)
      suf[i][j] = pmax(suf[i][j - 1], val[i >> j]);
  }
  for (int i = 2; i < M + M; ++i) lg[i] = lg[i >> 1] + 1;
  for (int l, r; m; --m) {
    scanf("%d%d", &l, &r), l += M - 1, r += M + 1;
    int L = qlink(l, lg[l ^ r] - 1).first;
    int R = qlink(r, lg[l ^ r] - 1).second;
    printf("%d\n", max(L, R));
  }
  //接下来应该要有一些手动释放内存的部分（可以 vector 实现然后省掉）。
  //但是测试 OJ 上不允许手动释放，并且程序终止时本身就会自动释放，所以没了。
  return 0;
}

缺点是常数略大，优点是复杂度漂亮。

是博主（至少自认为）原创的，鉴于博主孤陋寡闻，如果已有同样数据结构还请不吝告知。

以上。