SegmentTreePractice

SegmentTreePractice1.java

/**
 * 練習問題1
 *
 * - i 番目の値を v に変更する。(update)
 * - l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、インデックスの合計を出力。(min)
 */
public class SegmentTreePractice1 {
    int N;
    int M;

    // 区間が持つ値
    static class NodeValue {
        // 最小値
        int min;

        // インデックスの和
        long minIndexSum;

        public NodeValue(int m, long i) {
            min = m;
            minIndexSum = i;
        }

        public NodeValue clone() {
            return new NodeValue(min, minIndexSum);
        }

        public static NodeValue zero() {
            return new NodeValue(Integer.MAX_VALUE, 0);
        }
    }

    NodeValue[] values;

    public SegmentTreePractice1(int[] data) {
        // 実装の都合上、最下段のノード数を2の乗数にする
        N = Integer.highestOneBit(data.length-1)<<2;

        // M : 最下段の左端のインデックス
        M = (N >> 1) - 1;

        values = new NodeValue[N];
        for (int i = 0 ; i < data.length ; i++) {
            // 最下段を初期化
            values[M+i] = new NodeValue(data[i], i);
        }
        for (int i = M+data.length ; i < N ; i++) {
            // 余白をゼロ値で埋める
            values[i] = NodeValue.zero();
        }

        for (int i = M-1 ; i >= 0 ; i--) {
            // 初期化のため、上の段についてマージ処理を呼ぶ。
            // i*2+1 : i番目の左の子
            // i*2+2 : i番目の右の子
            values[i] = merge(values[i*2+1], values[i*2+2]);
        }
    }

    /**
     * マージ処理
     */
    public NodeValue merge(NodeValue left, NodeValue right) {
        if (left.min == right.min) {
            return new NodeValue(left.min, left.minIndexSum + right.minIndexSum);
        } else if (left.min < right.min) {
            return left.clone();
        } else {
            return right.clone();
        }
    }

    /**
     * クエリ1: idx番目の値をvalueに更新。
     */
    public void update(int idx, int value) {
        values[M+idx].min = value;
        int i = M+idx;
        while (true) {
            // 親に移動
            i = (i-1) >> 1;

            // 親の更新をするため、マージ処理を呼ぶ
            values[i] = merge(values[i*2+1], values[i*2+2]);

            // 一番上まで到達したら抜ける
            if (i == 0) {
                break;
            }
        }
    }

    /**
     * クエリ2: [l,r)の最小値と、そのインデックスの和を求める。
     */
    public NodeValue min(int l, int r) {
        return min(l, r, 0, 0, M+1);
    }

    private NodeValue min(int l, int r, int idx, int fr, int to) {
        if (to <= l || r <= fr) {
            // クエリの指定区間外ならゼロ値を返す
            return NodeValue.zero();
        }
        if (l <= fr && to <= r) {
            // 今の区間がクエリの指定区間にすっぽり入ってたら、その区間の値を返す
            return values[idx].clone();
        }

        // med: 現在の区間の中間。最初に呼ぶ M+1 は 2の乗数になってるので、必ず割り切れる
        int med = (fr+to) / 2;

        // 左の区間について答えを求める
        NodeValue left = min(l, r, idx*2+1, fr, med);

        // 右の区間について答えを求める
        NodeValue right = min(l, r, idx*2+2, med, to);

        // 左右の結果をマージする
        return merge(left, right);
    }
}

SegmentTreePractice2.java

import java.util.Arrays;

/**
 * 練習問題2
 *
 * - i 番目の値を v に変更する。(update)
 * - l 番目から r 番目の値の中で、最も左端で v 以下になるインデックスを求める。(findIndexLessThanV)
 */
public class SegmentTreePractice2 {
    int N;
    int M;
    int[] seg;

    public SegmentTreePractice2(int[] data) {
        N = Integer.highestOneBit(data.length-1)<<2;
        M = (N >> 1) - 1;

        seg = new int[N];
        Arrays.fill(seg, Integer.MAX_VALUE);
        for (int i = 0 ; i < data.length ; i++) {
            seg[M+i] = data[i];
        }
        for (int i = M-1 ; i >= 0 ; i--) {
            seg[i] = compute(i);
        }
    }

    /**
     * Uodates value at position minIndexSum.
     *
     * @param idx
     * @param value
     */
    public void update(int idx, int value) {
        seg[M+idx] = value;
        int i = M+idx;
        while (true) {
            i = (i-1) >> 1;
            seg[i] = compute(i);
            if (i == 0) {
                break;
            }
        }
    }

    private int compute(int i) {
        return Math.min(seg[i*2+1], seg[i*2+2]);
    }

    public int findIndexLessThanV(int l, int r, int v) {
        int ret = findIndexLessThanV(l, r, 0, 0, M+1, v);
        if (ret == Integer.MAX_VALUE) {
            return -1;
        }
        return ret;
    }

    private int findIndexLessThanV(int l, int r, int idx, int fr, int to, int v) {
        // 区間外
        if (to <= l || r <= fr) {
            return Integer.MAX_VALUE;
        }

        // vよりでかい
        if (seg[idx] > v) {
            return Integer.MAX_VALUE;
        }

        // ここ以下、必ず答えが存在

        int med = (fr+to) / 2;
        if (l <= fr && to <= r) {
            int len = to-fr;
            if (len == 1) {
                // 最下段
                return idx-M;
            }
        }

        int left = findIndexLessThanV(l, r, idx*2+1, fr, med, v);

        if (left < Integer.MAX_VALUE) {
            // 左の答えがINFでないなら左を優先して返す
            return left;
        } else {
            // 左に無いなら、右に必ず答えがある
            return findIndexLessThanV(l, r, idx*2+2, med, to, v);
        }
    }
}

SegmentTreePractice3.java

/**
 * 練習問題3
 *
 * - l 番目から r 番目の値を v に変更する。(update)
 * - l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、最も左端のインデックスを求めること。(min)
 */
public class SegmentTreePractice3 {
    static final int INF = 1000000010;

    int N;
    int M;

    // 区間が持つ値
    static class NodeValue {
        // 最小値
        int min;

        // 最左インデックス
        int minIndex;

        // 遅延評価中の最小値
        int delayMin;

        // 遅延評価中の最左インデックス
        int delayMinIndex;


        public NodeValue(int m, int idx) {
            min = m;
            minIndex = idx;
            delayMin = INF;
            delayMinIndex = INF;
        }

        public NodeValue clone() {
            return new NodeValue(min, minIndex);
        }

        public static NodeValue zero() {
            return new NodeValue(Integer.MAX_VALUE, 0);
        }
    }

    NodeValue[] values;

    public SegmentTreePractice3(int[] data) {
        // 実装の都合上、最下段のノード数を2の乗数にする
        N = Integer.highestOneBit(data.length-1)<<2;

        // M : 最下段の左端のインデックス
        M = (N >> 1) - 1;

        values = new NodeValue[N];
        for (int i = 0 ; i < data.length ; i++) {
            // 最下段を初期化
            values[M+i] = new NodeValue(data[i], i);
        }
        for (int i = M+data.length ; i < N ; i++) {
            // 余白をゼロ値で埋める
            values[i] = NodeValue.zero();
        }

        for (int i = M-1 ; i >= 0 ; i--) {
            // 初期化のため、上の段についてマージ処理を呼ぶ。
            // i*2+1 : i番目の左の子
            // i*2+2 : i番目の右の子
            values[i] = merge(values[i*2+1], values[i*2+2]);
        }
    }

    /**
     * マージ処理
     */
    public NodeValue merge(NodeValue left, NodeValue right) {
        if (left.min <= right.min) {
            return left.clone();
        } else {
            return right.clone();
        }
    }

    /**
     * 遅延評価中の値があれば適用しつつ子供に下ろす
     */
    public void pushDown(int idx, int fr, int to) {
        if (values[idx].delayMin == INF) {
            // 遅延評価してないし
            return;
        }

        // 自分に適用
        values[idx].min = values[idx].delayMin;
        values[idx].minIndex = values[idx].delayMinIndex;

        if (idx >= M) {
            // 最下段には子がいないので終了
            return;
        }
        // 左右の子に下ろす
        int left = idx*2+1;
        int right = idx*2+2;

        // 左の子の最左位置は fr
        values[left].delayMin = values[idx].delayMin;
        values[left].delayMinIndex = fr;


        // 右の子の最左位置は fr と to の中間
        values[right].delayMin = values[idx].delayMin;
        values[right].delayMinIndex = (fr + to) / 2;

        // 遅延評価してない状態にリセット
        values[idx].delayMin = INF;
        values[idx].delayMinIndex = INF;
    }

    /**
     * 左右の子のデータを吸い上げて適用する。
     */
    public void pullUp(int idx) {
        NodeValue newValue = merge(values[idx*2+1], values[idx*2+2]);
        values[idx].min = newValue.min;
        values[idx].minIndex = newValue.minIndex;
    }

    /**
     * クエリ1: [l,r)の値を v に更新する。
     */
    public void update(int l, int r, int v) {
        update(l, r, v, 0, 0, M+1);
    }

    public void update(int l, int r, int v, int idx, int fr, int to) {
        // 遅延評価中の値を持っていた場合、子供に下ろす
        pushDown(idx, fr, to);

        if (to <= l || r <= fr) {
            return;
        }
        if (l <= fr && to <= r) {
            // 遅延評価中の値を積む
            values[idx].delayMin = v;
            values[idx].delayMinIndex = fr;

            // 子に下ろす
            pushDown(idx, fr, to);
            return;
        }

        // 左右の子を更新
        int med = (fr + to) / 2;
        update(l, r, v, idx*2+1, fr, med);
        update(l, r, v, idx*2+2, med, to);

        // 左右の子の現在の値が `min`, `minIndex` に入ってるため、吸い上げる
        pullUp(idx);
    }


    /**
     * クエリ2: [l,r)の最小値と、そのインデックスの和を求める。
     */
    public NodeValue min(int l, int r) {
        return min(l, r, 0, 0, M+1);
    }

    private NodeValue min(int l, int r, int idx, int fr, int to) {
        // 遅延評価中の値を持っていた場合、子供に下ろす
        pushDown(idx, fr, to);

        if (to <= l || r <= fr) {
            // クエリの指定区間外ならゼロ値を返す
            return NodeValue.zero();
        }

        if (l <= fr && to <= r) {
            // 今の区間がクエリの指定区間にすっぽり入ってたら、その区間の値を返す
            return values[idx].clone();
        }

        // med: 現在の区間の中間。最初に呼ぶ M+1 は 2の乗数になってるので、必ず割り切れる
        int med = (fr+to) / 2;

        // 左の区間について答えを求める
        NodeValue left = min(l, r, idx*2+1, fr, med);

        // 右の区間について答えを求める
        NodeValue right = min(l, r, idx*2+2, med, to);

        // 左右の子の現在の値が `min`, `minIndex` に入ってるため、吸い上げる
        pullUp(idx);

        // 左右の結果をマージする
        return merge(left, right);
    }
}