動的セグ木 (dynamic_segtree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-14 02:50:33+09:00
• Include: #include "dynamic_segtree.hpp"

座圧せずに使えるセグ木。

コンストラクタ

DynamicSegtree<S, op, e>(long long lmin, long long rmax)

取りうる index の区間を設定し、空のセグ木を構築。以降、$L=\mathrm{rmax}-\mathrm{lmin}$ とする。

計算量

• $O(1)$

set

void set(long long p, S x)

p 番目の要素を x に設定。

計算量

• $O(\log L)$

get

S get(long long p)

p 番目の要素を取得。

計算量

• $O(\log L)$

prod

S prod(long long l, long long r)

区間 $[l, r)$ の総積を取得。

計算量

• $O(\log L)$

max_right

template <class F>
long long max_right(long long l, F f) 

以下の条件を両方満たす r を返す。

• r = l もしくは f(op[l, r)) = true
• r = rmax もしくは f(op[l, r + 1)) = false

f が単調ならば、f(op[l, r)) = true となる最大の r と解釈できる。

計算量

• $O(\log L)$

min_left

template <class F>
long long min_left(long long r, F f)

以下の条件を両方満たす l を返す。

• l = r もしくは f(op[l, r)) = true
• l = lmin もしくは f(op[l - 1, r)) = false

f が単調ならば、f(op[l, r)) = true となる最小の l と解釈できる。

計算量

• $O(\log L)$

Verified with

• test/aoj_dsl_a_range_minimum_query.cpp
• test/aoj_dsl_b_range_sum_query.cpp
• test/lc_point_set_range_composite.cpp
• test/lc_point_set_range_composite_large.cpp

Code

template <class S, auto op, auto e>
class DynamicSegtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>, "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>, "e must work as S()");

   public:
    DynamicSegtree(long long lmin, long long rmax) : lmin(lmin), rmax(rmax), root(nullptr) { assert(lmin <= rmax); }

    void set(long long p, S x) {
        assert(lmin <= p && p <= rmax);
        set(root, lmin, rmax, p, x);
    }

    S get(long long p) {
        assert(lmin <= p && p <= rmax);
        return get(root, lmin, rmax, p);
    }

    S prod(long long l, long long r) {
        assert(lmin <= l && l <= r && r <= rmax);
        return prod(root, lmin, rmax, l, r);
    }

    template <class F>
    long long max_right(long long l, F f) {
        assert(lmin <= l && l <= rmax);
        S sm = e();
        return max_right(root, lmin, rmax, l, f, sm);
    }

    template <class F>
    long long min_left(long long r, F f) {
        assert(lmin <= r && r <= rmax);
        S sm = e();
        return min_left(root, lmin, rmax, r, f, sm);
    }

   private:
    struct Node;
    using Node_t = unique_ptr<Node>;
    struct Node {
        S val;
        Node_t l, r;

        Node(S v) : val(v), l(nullptr), r(nullptr) {}
    };

    S get(const Node_t &t) { return (t == nullptr ? e() : t->val); }

    long long lmin, rmax;
    Node_t root;

    void set(Node_t &t, long long l, long long r, long long p, S x) {
        if (t == nullptr) t = make_unique<Node>(e());
        if (l + 1 == r) {
            t->val = x;
            return;
        }

        long long m = (l + r) >> 1;  // [l, m) [m, r)
        if (p < m)
            set(t->l, l, m, p, x);
        else
            set(t->r, m, r, p, x);

        t->val = op(get(t->l), get(t->r));
    }

    S get(const Node_t &t, long long l, long long r, long long p) {
        if (t == nullptr) return e();
        if (l + 1 == r) return t->val;
        long long m = (l + r) >> 1;
        if (p < m) return get(t->l, l, m, p);
        return get(t->r, m, r, p);
    }

    // query: [l, r), now: [a, b)
    S prod(const Node_t &t, long long a, long long b, long long l, long long r) {
        if (t == nullptr || b <= l || r <= a) return e();
        if (l <= a && b <= r) return t->val;
        long long c = (a + b) >> 1;
        return op(prod(t->l, a, c, l, r), prod(t->r, c, b, l, r));
    }

    // test: [a, b)
    // sm: f(sm) = true
    template <class F>
    long long max_right(const Node_t &t, long long a, long long b, long long l, F f, S &sm) {
        if (t == nullptr || b <= l) return rmax;
        if (l <= a && f(op(sm, t->val))) {
            sm = op(sm, t->val);
            return rmax;  // f(op[l, b)) = true
        }
        if (a + 1 == b) return a;  // f(op(sm, dat[a])) = false
        long long c = (a + b) >> 1;
        long long l_test = max_right(t->l, a, c, l, f, sm);
        if (l_test != rmax) return l_test;
        return max_right(t->r, c, b, l, f, sm);
    }

    // test: [a, b)
    // sm: f(sm) = true
    template <class F>
    long long min_left(const Node_t &t, long long a, long long b, long long r, F f, S &sm) {
        if (t == nullptr || r <= a) return lmin;
        if (b <= r && f(op(t->val, sm))) {
            sm = op(t->val, sm);
            return lmin;  // f(op[a, r)) = true
        }
        if (a + 1 == b) return b;  // f(op(dat[b - 1], sm)) = false
        long long c = (a + b) >> 1;
        long long r_test = min_left(t->r, c, b, r, f, sm);
        if (r_test != lmin) return r_test;
        return min_left(t->l, a, c, r, f, sm);
    }
};

#line 1 "dynamic_segtree.hpp"
template <class S, auto op, auto e>
class DynamicSegtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>, "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>, "e must work as S()");

   public:
    DynamicSegtree(long long lmin, long long rmax) : lmin(lmin), rmax(rmax), root(nullptr) { assert(lmin <= rmax); }

    void set(long long p, S x) {
        assert(lmin <= p && p <= rmax);
        set(root, lmin, rmax, p, x);
    }

    S get(long long p) {
        assert(lmin <= p && p <= rmax);
        return get(root, lmin, rmax, p);
    }

    S prod(long long l, long long r) {
        assert(lmin <= l && l <= r && r <= rmax);
        return prod(root, lmin, rmax, l, r);
    }

    template <class F>
    long long max_right(long long l, F f) {
        assert(lmin <= l && l <= rmax);
        S sm = e();
        return max_right(root, lmin, rmax, l, f, sm);
    }

    template <class F>
    long long min_left(long long r, F f) {
        assert(lmin <= r && r <= rmax);
        S sm = e();
        return min_left(root, lmin, rmax, r, f, sm);
    }

   private:
    struct Node;
    using Node_t = unique_ptr<Node>;
    struct Node {
        S val;
        Node_t l, r;

        Node(S v) : val(v), l(nullptr), r(nullptr) {}
    };

    S get(const Node_t &t) { return (t == nullptr ? e() : t->val); }

    long long lmin, rmax;
    Node_t root;

    void set(Node_t &t, long long l, long long r, long long p, S x) {
        if (t == nullptr) t = make_unique<Node>(e());
        if (l + 1 == r) {
            t->val = x;
            return;
        }

        long long m = (l + r) >> 1;  // [l, m) [m, r)
        if (p < m)
            set(t->l, l, m, p, x);
        else
            set(t->r, m, r, p, x);

        t->val = op(get(t->l), get(t->r));
    }

    S get(const Node_t &t, long long l, long long r, long long p) {
        if (t == nullptr) return e();
        if (l + 1 == r) return t->val;
        long long m = (l + r) >> 1;
        if (p < m) return get(t->l, l, m, p);
        return get(t->r, m, r, p);
    }

    // query: [l, r), now: [a, b)
    S prod(const Node_t &t, long long a, long long b, long long l, long long r) {
        if (t == nullptr || b <= l || r <= a) return e();
        if (l <= a && b <= r) return t->val;
        long long c = (a + b) >> 1;
        return op(prod(t->l, a, c, l, r), prod(t->r, c, b, l, r));
    }

    // test: [a, b)
    // sm: f(sm) = true
    template <class F>
    long long max_right(const Node_t &t, long long a, long long b, long long l, F f, S &sm) {
        if (t == nullptr || b <= l) return rmax;
        if (l <= a && f(op(sm, t->val))) {
            sm = op(sm, t->val);
            return rmax;  // f(op[l, b)) = true
        }
        if (a + 1 == b) return a;  // f(op(sm, dat[a])) = false
        long long c = (a + b) >> 1;
        long long l_test = max_right(t->l, a, c, l, f, sm);
        if (l_test != rmax) return l_test;
        return max_right(t->r, c, b, l, f, sm);
    }

    // test: [a, b)
    // sm: f(sm) = true
    template <class F>
    long long min_left(const Node_t &t, long long a, long long b, long long r, F f, S &sm) {
        if (t == nullptr || r <= a) return lmin;
        if (b <= r && f(op(t->val, sm))) {
            sm = op(t->val, sm);
            return lmin;  // f(op[a, r)) = true
        }
        if (a + 1 == b) return b;  // f(op(dat[b - 1], sm)) = false
        long long c = (a + b) >> 1;
        long long r_test = min_left(t->r, c, b, r, f, sm);
        if (r_test != lmin) return r_test;
        return min_left(t->l, a, c, r, f, sm);
    }
};

Back to top page