本文将简介如何优雅地在 zkw 线段树上跑无修 rmq。

核心：数据结构优化线段树。

普通的 zkw 线段树解法分为线性建树和单次 $O(\log n)$ 的查询，显然查询是瓶颈。

观察 zkw 线段树的查询结构：

  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]);
  }

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

它是可以快速合并的，直接采用倍增优化（树上 ST 表），然后 $O(1)$ 回答询问。

由于树高 $O(\log n)$，故预处理 ST 的时空复杂度均为 $O(n\log\log n)$。

甚至可以原线段树都不要了，直接用数组建出 ST 表（见代码）。

综上，预处理时间复杂度：$O(n\log\log n)$，单次查询复杂度 $O(1)$，空间复杂度 $O(n\log\log n)$，优点是代码较短。

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

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9, Mx = 1 << 17;
int n, m, M = 1, lg[Mx << 1];
pair<int, int> val[Mx << 1][5];
int main() {
  scanf("%d%d", &n, &m);
  while (M <= n) M <<= 1;
  for (int i = M + 1, a; i <= M + n; ++i) {
    scanf("%d", &a);
    ((i & 1) ? val[i ^ 1][0].first : val[i ^ 1][0].second) = a;
  }
  for (int i = M - 1; i > 1; --i)
    ((i & 1) ? val[i ^ 1][0].first : val[i ^ 1][0].second) =
        max(val[i << 1][0].first, val[i << 1 | 1][0].second);
  for (int i = 2; i < M + M; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i = 2; i < M + M; ++i)
    for (int h = 1; h < 5; ++h) {
      val[i][h].first =
          max(val[i][h - 1].first, val[i >> (1 << (h - 1))][h - 1].first);
      val[i][h].second =
          max(val[i][h - 1].second, val[i >> (1 << (h - 1))][h - 1].second);
    }
  for (int l, r, len; m; --m) {
    scanf("%d%d", &l, &r);
    l += M - 1, r += M + 1, len = lg[l ^ r];
    printf("%d\n", max(max(val[l][lg[len]].first,
                           val[l >> (len - (1 << lg[len]))][lg[len]].first),
                       max(val[r][lg[len]].second,
                           val[r >> (len - (1 << lg[len]))][lg[len]].second)));
  }
  return 0;
}

（注：其实也可以类似复杂度用于维护其它类似信息比如区间或。

维护不可随意重叠的信息如区间乘积取模时查询复杂度 $O(\log\log n)$，预处理复杂度和空间复杂度不变。）