segtree
(Datastructure/segtree.hpp)

• View this file on GitHub
• Last update: 2024-07-06 20:37:29+09:00
• Include: #include "Datastructure/segtree.hpp"

概要

ACL の segtreeと同じ 参考 : https://github.com/atcoder/ac-library

省略できるもの

max_right, min_leftの実装は他の機能と独立であり、省略できます。

関数

• set(int p, S x)…a[p]にxを代入
• prod(int l, int r)…[l, r)の演算結果を返す
• get(int p)…a[p]を返す
• all_prod() …op(a[0], … ,a[n-1])を返す

• max_right<F>(int l, F f) … fが単調ならば、f(op(a[l], … , a[r-1])) = true となる最大のr
  特に、
  (1) f(op(a[l])) = falseの場合 … lを返す
  (2) f(op(a[l], … , a[n-1])) = falseの場合 … nを返す

  • 制約 ・ f(e()) = true ・$0 \le l \le n$
• min_left<F>(int r, F f) … fが単調ならば、f(op(a[l], … , a[r-1]))がtrueとなる最小のl
  特に、
  (1) f(op(a[r-1])) = falseの場合 … rを返す
  (2) f(op(a[0], … , a[r-1])) = trueの場合… 0を返す
  • 制約 ・ f(e()) = true ・$0 \le r \le n$

Verified with

• verify/Datastructure_compress.test.cpp
• verify/Datastructure_seg_prod.test.cpp
• verify/Datastructure_segtree.test.cpp
• verify/hld.test.cpp
• verify/mo.test.cpp

Code

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
    int n;
    int sz;
    vector<S> d;

    segtree(int n) : segtree(vector<S>(n, e())) {}

    segtree(const vector<S> &v) : n((int)v.size()), sz(1) {
        while(sz < n) sz <<= 1;
        d.resize(2*sz, e());
        rep(i, 0, n) {
            d[sz+i] = v[i];
        }
        rrep(i, 1, sz) d[i] = op(d[i<<1], d[i<<1|1]);
    }

    void set(int p, S x) {
        assert(0 <= p && p < n);
        p += sz;
        d[p] = x;
        while(p > 1) {
            p >>= 1;
            d[p] = op(d[p<<1], d[p<<1|1]);
        }
    }

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

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        S sml = e(), smr = e();
        l += sz;
        r += sz;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

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

    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= n);
        assert(f(e()));
        if (l == n) return n;
        l += sz;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < sz) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - sz;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return n;
    }

    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= n);
        assert(f(e()));
        if (r == 0) return 0;
        r += sz;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < sz) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - sz;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
    
};
/*
@brief segtree
@docs doc/segtree.md
*/

#line 1 "Datastructure/segtree.hpp"
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
    int n;
    int sz;
    vector<S> d;

    segtree(int n) : segtree(vector<S>(n, e())) {}

    segtree(const vector<S> &v) : n((int)v.size()), sz(1) {
        while(sz < n) sz <<= 1;
        d.resize(2*sz, e());
        rep(i, 0, n) {
            d[sz+i] = v[i];
        }
        rrep(i, 1, sz) d[i] = op(d[i<<1], d[i<<1|1]);
    }

    void set(int p, S x) {
        assert(0 <= p && p < n);
        p += sz;
        d[p] = x;
        while(p > 1) {
            p >>= 1;
            d[p] = op(d[p<<1], d[p<<1|1]);
        }
    }

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

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        S sml = e(), smr = e();
        l += sz;
        r += sz;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

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

    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= n);
        assert(f(e()));
        if (l == n) return n;
        l += sz;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < sz) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - sz;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return n;
    }

    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= n);
        assert(f(e()));
        if (r == 0) return 0;
        r += sz;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < sz) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - sz;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
    
};
/*
@brief segtree
@docs doc/segtree.md
*/

Back to top page