在正常的 \(n\) 的范围内（比如 \(n\le 2^{64}\)），可以做到空间和预处理都是 \(O(n)\) 的，询问是 \(O(1)\)。
考虑每 \(B\) 个点一个块，\(B\) 大概为 \(log_2 n\)。对块做正常的 ST 表，再预处理每个块的前缀和后缀最值。
对于询问不在一个块的很好做，考虑在一个块的。预处理单调队列，当前加入完了 \(r\)，用 \(w_r\) 表示 \([r - B + 1, r]\) 中在队列中的点，询问是简单的。
在正常的 \(n\) 的范围内（比如 \(n\le 2^{64}\)），可以做到空间和预处理都是 \(O(n)\) 的，询问是 \(O(1)\)。
考虑每 \(B\) 个点一个块，\(B\) 大概为 \(log_2 n\)。对块做正常的 ST 表，再预处理每个块的前缀和后缀最值。
对于询问不在一个块的很好做，考虑在一个块的。预处理单调队列，当前加入完了 \(r\)，用 \(w_r\) 表示 \([r - B + 1, r]\) 中在队列中的点，询问是简单的。