Segtree
(Data_structure/Segtree.hpp)

• View this file on GitHub
• Last update: 2023-07-23 08:43:48+00:00
• Include: #include "Data_structure/Segtree.hpp"

セグメント木 モノイドを渡す

モノイド

集合 $S$ とその二項演算 $\cdot : S \times S \to S$ で、

• $\forall a, b, c \in S~~(a \cdot b) \cdot c = a \cdot (b \cdot c)$
• $\exist e \in S\mathrm{s.t.}\forall a \in S~~ e \cdot a = a \cdot e = a$

を満たすとき、$(S, \cdot, e)$ をモノイドという。

例えば加法モノイドなら、次のように書く。

struct Add_M {
    using T = long long;
    static T e() { return 0; }
    static T op(T x, T y) { return x + y; }
};

Tはモノイドの型名。e()は単位元、op(T x, T y)は二項演算を返すようにする。

コンストラクタ

(1) Segtree<Monoid> seg(int N)
(2) Segtree<Monoid> seg(vector<Monoid::T> v)

• (1): 長さNですべてMonoid::e()の数列で初期化
• (2): vの内容で初期化

計算量

• $O(N)$

set

void seg.set(int p, Monoid::T x)

a[p]にxを代入する。

制約

• $0 \leq p < N$

計算量

• $O(\log N)$

get

Monoid::T seg.get(int p)

a[p]の値を取得する。

制約

• $0 \leq p < N$

計算量

• $O(1)$

prod

Monoid::T seg.prod(int l, int r)

Monoid::op(a[l], ..., a[r-1])を返す。$l = r$の時はMonoid::e()が返る。

制約

• $0 \leq l \leq r \leq N$

計算量

• $O(\log N)$

all_prod

Monoid::T seg.all_prod()

Monoid::op(a[0], ..., a[n-1])を返す。

計算量

• $O(1)$

TODO: セグ木上の二分探索

使いそうなモノイド

加法モノイド(区間和取得)

struct Add_M {    
    using T = long long;
    static T e() { return 0; }
    static T op(T x, T y) { return x + y; }
};

最大モノイド(区間最大取得)

struct Max_M {    
    using T = long long;
    static T e() { return -INF; }
    static T op(T x, T y) { return max(x, y); }
};

最小モノイド(区間最小取得)

struct Min_M {    
    using T = long long;
    static T e() { return INF; }
    static T op(T x, T y) { return min(x, y); }
};

テンプレート

struct Monoid {
    using T = T;
    static T e() { return e; }
    static T op(T x, T y) { return op(x, y); }
}

Verified with

• Test/yosupo-Point-Add-Range-Sum.test.cpp

Code

template<class M> struct Segtree {
  public:
    using S = typename M::T;

    Segtree() : Segtree(0) {}
    Segtree(int n) : Segtree(vector<S> (n, M::e())) {}
    Segtree(const vector<S> &v) : n(int(v.size())) { 
        while((1 << log) < n) log++;
        size = 1 << log;
        d = vector<S> (2 * size, M::e());
        for(int i = 0; i < n; i++) d[size + i] = v[i];
        for(int i = size - 1; i >= 1; i--) update(i);
    }

    void set(int p, S x) {
        assert(0 <= p && p < n);
        p += size;
        d[p] = x;
        for(int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        S sml = M::e(), smr = M::e();
        l += size; r += size;
        while(l < r) {
            if(l & 1) sml = M::op(sml, d[l++]);
            if(r & 1) smr = M::op(d[--r], smr);
            l >>= 1; r >>= 1;
        }
        return M::op(sml, smr);
    }

    S all_prod(){ return d[1]; }


  private:
    int n, size, log = 0;
    vector<S> d;
    void update(int k){ d[k] = M::op(d[k * 2], d[k * 2 + 1]); }

};

#line 1 "Data_structure/Segtree.hpp"
template<class M> struct Segtree {
  public:
    using S = typename M::T;

    Segtree() : Segtree(0) {}
    Segtree(int n) : Segtree(vector<S> (n, M::e())) {}
    Segtree(const vector<S> &v) : n(int(v.size())) { 
        while((1 << log) < n) log++;
        size = 1 << log;
        d = vector<S> (2 * size, M::e());
        for(int i = 0; i < n; i++) d[size + i] = v[i];
        for(int i = size - 1; i >= 1; i--) update(i);
    }

    void set(int p, S x) {
        assert(0 <= p && p < n);
        p += size;
        d[p] = x;
        for(int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        S sml = M::e(), smr = M::e();
        l += size; r += size;
        while(l < r) {
            if(l & 1) sml = M::op(sml, d[l++]);
            if(r & 1) smr = M::op(d[--r], smr);
            l >>= 1; r >>= 1;
        }
        return M::op(sml, smr);
    }

    S all_prod(){ return d[1]; }


  private:
    int n, size, log = 0;
    vector<S> d;
    void update(int k){ d[k] = M::op(d[k * 2], d[k * 2 + 1]); }

};

Back to top page