RangeMin.java (範囲最小値を取得)

Main.java

import java.util.*;

final class Main {
    static final int TEST = 100;
    static final int N_MIN = 100;
    static final int N_MAX = 999;

    public static void main(String[] args) throws Exception {
        long t0 = System.currentTimeMillis();

        Random rand = new Random(System.currentTimeMillis());

        for (int t = 1; t <= TEST; t++) {
            int N = rand.nextInt(N_MAX - N_MIN + 1) + N_MIN;
            System.err.printf("[TEST] %3d/%3d N=%d : ", t, TEST, N);

            List<Integer> list = new ArrayList<>(N);
            for (int i = 1; i <= N; i++) list.add(i);

            for (int i = 0; i < 5; i++)
                Collections.shuffle(list, rand);

            List<Integer> res0 = new ArrayList<>(N * N);
            long time0 = System.currentTimeMillis();
            {
                RangeMin<Integer> rm = new RangeMin<>(list, (a, b) -> a.compareTo(b));

                for (int i = 0; i < list.size(); i++) {
                    for (int k = i; k < list.size(); k++) {
                        res0.add(rm.getMin(i, k));
                    }
                }
            }
            long time1 = System.currentTimeMillis();

            List<Integer> res1 = new ArrayList<>(N * N);
            long time2 = System.currentTimeMillis();
            {
                for (int i = 0; i < list.size(); i++) {
                    for (int k = i; k < list.size(); k++) {
                        Integer y = list.get(k);
                        for (int e = i; e < k; e++) {
                            if (list.get(e).compareTo(y) <= 0)
                                y = list.get(e);
                        }
                        res1.add(y);
                    }
                }
            }
            long time3 = System.currentTimeMillis();

            int pos = 0;
            for (int i = 0; i < list.size(); i++) {
                for (int k = i; k < list.size(); k++) {
                    Integer x = res0.get(pos);
                    Integer y = res1.get(pos);
                    if (!y.equals(x)) {
                        System.err.println("NG");
                        System.err.println(Arrays.toString(list.toArray(new Integer[0])));
                        throw new RuntimeException("[invalid] expect:" + y + ", getMin("+i+","+k+")=" + x);
                    }
                    pos++;
                }
            }

            System.err.printf("OK ( %7d ms / %7d ms )%n", time1 - time0, time3 - time2);
        }

        long t1 = System.currentTimeMillis();
        System.err.printf("ALL DONE ( %10d ms )%n", t1 - t0);
    }
}

RangeMin.java

class RangeMin<T> {
    java.util.List<java.util.List<T>> table;
    int[][] starts, ends;

    java.util.Comparator<? super T> cmp;

    RangeMin(java.util.List<T> base, java.util.Comparator<? super T> cmp) {
        this.cmp = cmp;
        table = new java.util.ArrayList<>();
        java.util.List<int[]> starts = new java.util.ArrayList<>();
        java.util.List<int[]> ends = new java.util.ArrayList<>();
        int[] tts = new int[base.size()], tte = new int[base.size()];
        for (int i = 0; i < base.size(); i++) {
            tts[i] = tte[i] = i;
        }
        starts.add(tts);
        ends.add(tte);
        table.add(base);
        while (base.size() > 1) {
            int b = (base.size() + 1) / 2;
            java.util.List<T> tmp = new java.util.ArrayList<>(b);
            int[] ts = new int[b], te = new int[b];
            for (int i = 0; i < base.size(); i += 2) {
                if (i + 1 < base.size()) {
                    T v1 = base.get(i), v2 = base.get(i + 1);
                    tmp.add(cmp.compare(v1, v2) <= 0 ? v1 : v2);
                    ts[i >> 1] = tts[i];
                    te[i >> 1] = tte[i + 1];
                } else {
                    tmp.add(base.get(i));
                    ts[i >> 1] = tts[i];
                    te[i >> 1] = tte[i];
                }
            }
            table.add(tmp);
            base = tmp;
            starts.add(ts);
            tts = ts;
            ends.add(te);
            tte = te;
        }
        java.util.Collections.reverse(starts);
        java.util.Collections.reverse(ends);
        this.starts = starts.toArray(new int[0][]);
        this.ends = ends.toArray(new int[0][]);
    }

    /**
     * @param endIndex  inclusive
     */
    T getMin(int startIndex, int endIndex) {
        if (startIndex == endIndex) {
            return table.get(0).get(startIndex);
        }
        return getMin(0, 0, startIndex, endIndex);
    }

    private T getMin(int p, int i, int startIndex, int endIndex) {
        if (starts[p][i] == startIndex && ends[p][i] == endIndex) {
            return table.get(table.size() - 1 - p).get(i);
        }
        if (endIndex <= ends[p + 1][i << 1]) {
            return getMin(p + 1, i << 1, startIndex, endIndex);
        }
        if (ends[p + 1][i << 1] < startIndex) {
            return getMin(p + 1, (i << 1) + 1, startIndex, endIndex);
        }
        T v1 = getMin(p + 1, i << 1, startIndex, ends[p + 1][i << 1]);
        T v2 = getMin(p + 1, (i << 1) + 1, starts[p + 1][(i << 1) + 1], endIndex);
        return cmp.compare(v1, v2) <= 0 ? v1 : v2;
    }
}