セグメント木

参考

プログラミングコンテストチャレンジブック [第2版] p.153-

セグメント木について - beet's soil

遅延評価セグメント木について - beet's soil

初心者の初心者による初心者のための典型segment tree - DEGwerの競技プログラミングと時々数学

セグメント木をソラで書きたいあなたに - hogecoder

遅延評価セグメント木をソラで書きたいあなたに - hogecoder

セグメント木

  • どういう写像が合成されていくか意識するのが大切

RMQセグメント木

#include <vector>
#include <climits>
using namespace std;
const int INF = INT_MAX;

// 0-indexed RMQ segment tree
class SegTree {
  private:
    int n;
    vector<int> dat;

  public:
    SegTree(int n_) {
        n = 1;
        while (n < n_)
            n *= 2;
        dat.assign(2 * n - 1, INF);
    }
    void update(int k, int a) {
        k += n - 1;
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
        }
    }
    int query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l)
            return INF;
        if (a <= l && r <= b)
            return dat[k];
        else {
            int vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
            int vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }
    // get min in [a, b)
    int query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};