RMQ

RMQ问题常用ST表或线段树来做（这里用线段树）

线段树求区间（ST表写法太难记了 +_+）

除此以外，线段树方便进行动态的修改，ST表的在线形式我也不太会搞 =_=

但是，虽然查询时间复杂度都是$O(\log _2n)$，但是ST表的倍增优势就是比线段树快

方法一：线段树

python版本

class Struct():
    def __init__(self):
        self.left = 0
        self.right = 0
        self.num = 0

def pushup(curNode):
    tr[curNode].num = max(tr[curNode << 1].num , tr[curNode << 1 | 1].num)

def build(curNode,L,R):
    if L == R:
        tr[curNode].left = L
        tr[curNode].rigth = R
        tr[curNode].num = data[L]
        return 
    tr[curNode].left = L
    tr[curNode].right = R
    mid = L + R >> 1
    build(curNode << 1,L,mid)
    build(curNode << 1 | 1,mid + 1,R)
    pushup(curNode)

def query(curNode,L,R):
    if tr[curNode].left >= L and tr[curNode].right <= R:
        return tr[curNode].num
    res = -float('inf')
    mid = tr[curNode].left + tr[curNode].right >> 1
    if L <= mid:
        res = max(query(curNode << 1,L,R),res)
    if R > mid:
        res = max(query(curNode << 1 | 1,L,R),res)
    return res

def modify(curNode,x,v):
    if tr[curNode].left == tr[curNode].right:
        tr[curNode].num = v
        return
    mid = tr[curNode].left + tr[curNode].right >> 1
    if x <= mid:
        modify(curNode << 1,x,v)
    if x > mid:
        modify(curNode << 1 | 1,x,v)
    pushup(curNode)


n = int(input())
data = [0] + [int(i) for i in input().split()]
tr = [Struct() for i in range(4*n + 1)]
build(1,1,n)

m = int(input())
for i in range(m):
    a,b = map(int,input().split())
    print(query(1,a,b))

方法二：ST表

妥协了，复制粘贴一下曾经写的代码放着给大家看吧

#ST算法(索引版)
#返回最大值索引版
from math import log as log
def ST_prework(n):
    for i in range(1,n+1):
        f[i][0] = i  #初始区间长度为2^0的阶段
    t = int(log(n,2)) + 1
    for j in range(1,t):
        for i in range(1,n - (1<<j) + 2):
            a = f[i][j-1]
            b = f[i + (1<<(j-1))][j-1]
            if arr[a] >= arr[b]: #这里一定要注意，一定是大于等于，因为如果两个数相等，我们要选前面一个，这样保证后面那个一样大小的数在需要时也能被选到
                f[i][j] = a
            else:
                f[i][j] = b


def ST_query(L,R):
    k = int(log(R - L + 1,2))
    a = f[L][k]
    b = f[R - (1<<k) + 1][k]
    if arr[a] >= arr[b]:
        return a
    else:
        return b



n = int(input())
arr = [0] + [int(i) for i in input().split()]
f = [[0]*(30) for i in range(n+1)]
data = []

ST_prework(n) #预处理

m = int(input())

for i in range(m):
    a,b = map(int,input().split())
    print(arr[ST_query(a,b)])