ホーム > libalgo

セグメントツリー (点 assign, 区間 min)

概要

セグメントツリーは区間を $O(\log N)$ 個に分割することで区間に対するクエリを高速に処理するデータ構造です.下の実装は RMQ (Range Minimum Query) です.

蟻本では query の引数にノードの番号,それが対応する区間,クエリの区間の全てを渡していますが,個人的にはノードの番号とそれに対する相対的な区間を渡すほうが好きです.

使い方

実装

template <typename T>
struct SegmentTree {
    static const int INF = std::numeric_limits<int>::max();
    int n;
    std::vector<T> dat;
    SegmentTree(int n_ = 0) : n(n_) {
        for (n = 1; n < n_; n <<= 1)
            ;
        dat.resize(n * 2, INF);
    }
    T query(int v, int w, int l, int r) const {
        if (r <= l || w == 0) return INF;
        if (r - l == w) return dat[v];  // assert(l == 0 && r == w);
        int m = w / 2;
        return min(query(v * 2, m, l, std::min(r, m)),
                   query(v * 2 + 1, m, std::max(0, l - m), r - m));
    }
    void update(int i, const T &x) {
        dat[i += n] = x;
        for (; i != 1; i /= 2) dat[i / 2] = min(dat[i], dat[i ^ 1]);
    }
    T query(int l, int r) { return query(1, n, l, r); }
};

検証

AOJ DSLA2 (Submission