数列区间最大值

线段树做法(5060 ms)

将线段树求sum的逻辑改为求max的逻辑即可

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 100010;
    static int[] w = new int[N];
    static class Node {
        int l, r, max;
        public Node (int l, int r, int max) {
            this(l, r);
            this.max = max;
        }

        public Node (int l, int r) {
            this.l = l;
            this.r = r;
        }
    }
    static Node[] tr = new Node[4 * N];
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]); m = Integer.parseInt(str[1]);

        String[] str2 = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) w[i] = Integer.parseInt(str2[i - 1]);
        build(1, 1, n);

        int l, r;
        while (m -- > 0) {
            String[] str3 = br.readLine().split(" ");
            l = Integer.parseInt(str3[0]);
            r = Integer.parseInt(str3[1]);
            out.println(query(1, l, r));
        }

        out.flush();
    }

    static void pushup(int u) {
        tr[u].max = Math.max(tr[u << 1].max, tr[u << 1 | 1].max);
    }

    static void build(int u, int l, int r) {
        if (l == r) tr[u] = new Node(l, r, w[r]);
        else {
            tr[u] = new Node(l, r);
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }

    static int query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].max;
        int mid = tr[u].l + tr[u].r >> 1;
        int max = Integer.MIN_VALUE;
        if (l <= mid) max = query(u << 1, l, r);
        if (r > mid) max = Math.max(max, query(u << 1 | 1, l, r));

        return max;
    }
}

RMQ(st表)(4113 ms)

另一道RMQ算法题 ：(有线段树的详细解读)天才的记忆 https://www.acwing.com/solution/content/259625/
f[i][j] : 表示l = i，长度为2^j次方的区间序列的最大值
即：区间[i, i + (1 << j))的最大值

import java.io.*;

public class Main {
    static final int N = 100010, M = 17;//2^17 = 13w > N
    static int[][] f = new int[N][M];
    static int[] a = new int[N];
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        str = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(str[i - 1]);
        init();

        int l, r;
        while (m -- > 0) {
            str = br.readLine().split(" ");
            l = Integer.parseInt(str[0]);
            r = Integer.parseInt(str[1]);
            int len = r - l + 1;
            int k = (int)(Math.log10(len) / Math.log10(2));//换底公式
            out.println(Math.max(f[l][k], f[r - (1 << k) + 1][k]));
        }

        out.flush();
    }

    static void init() {
        for (int j = 0; j < M; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                if (j == 0) f[i][0] = a[i];//该语句可以在输入的时候进行赋值
                else f[i][j] = Math.max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
    }
}