算法1

(线段树)

这题对用Python写的人来说实在是太不友好了，python运行过慢容易超时

build树

这道题算法还是用的线段树，但是在build树的时候，除了维护一个最大值之外，再维护一个最大值对应的编号。相当于建了两颗树，一颗记录最大值，一颗记录最大值对应的编号。以空间换取时间。

tree 记录最大值；tree_mark 记录最大值所对应的编号

 def build(u, l, r):   #记录最大值和最大值所对应的编号
    if l == r:
        tree[u] = arry[l]
        tree_mark[u] = l
        return 
    mid = (l+r)//2
    build(2*u, l, mid)
    build(2*u+1, mid+1, r)
    if tree[2*u] >= tree[2*u+1]:
        tree[u] = tree[2*u]
        tree_mark[u] = tree_mark[2*u]
    else:
        tree[u] = tree[2*u+1]
        tree_mark[u] = tree_mark[2*u+1]
    return

query

查询的时候可以通过判断当前根节点对应的最大值的编号是否在查询区间内，来判断是否进入下一层递归，如果最大值编号已经属于查询区间了直接输出最大值，有效的减少了无用的往下递归搜索。
s,t为要查询的左右区间值， l,r为当前根节点所包括的左右范围值

def query(u, s, t, l, r):   #查询区间最大值操作
    max_num = 0
    if tree_mark[u]>=s and tree_mark[u]<=t: #通过最大值编号是否在区间内结束递归
        return tree[u]
    mid = (l+r)//2
    if s<=mid:
        max_num = query(2*u, s, t, l, mid)
    if t>mid:
        ans = query(2*u+1, s, t, mid+1, r)
        if max_num <= ans:
            max_num = ans
    return max_num

python 完整代码

import sys


def build(u, l, r):   #记录最大值和最大值所对应的编号
    if l == r:
        tree[u] = arry[l]
        tree_mark[u] = l
        return 
    mid = (l+r)//2
    build(2*u, l, mid)
    build(2*u+1, mid+1, r)
    if tree[2*u] >= tree[2*u+1]:
        tree[u] = tree[2*u]
        tree_mark[u] = tree_mark[2*u]
    else:
        tree[u] = tree[2*u+1]
        tree_mark[u] = tree_mark[2*u+1]
    return


def query(u, s, t, l, r):   #查询区间最大值操作
    max_num = 0
    if tree_mark[u]>=s and tree_mark[u]<=t: #通过最大值编号是否在区间内结束递归
        return tree[u]
    mid = (l+r)//2
    if s<=mid:
        max_num = query(2*u, s, t, l, mid)
    if t>mid:
        ans = query(2*u+1, s, t, mid+1, r)
        if max_num <= ans:
            max_num = ans
    return max_num 


if __name__ == "__main__":
    n,m = list(map(int,sys.stdin.readline().strip().split()))
    arry = [0]+list(map(int,sys.stdin.readline().strip().split()))
    tree = [0 for i in range(4*n)]
    tree_mark = [0 for i in range(4*n)]
    build(1, 1, n)
    for i in range(m):
        a,b = list(map(int,sys.stdin.readline().strip().split()))
        print(query(1,a,b,1,n))