統合セグ木
(library/segtree/unified_segment_tree.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/segtree/unified_segment_tree.hpp"

統合セグ木

できること

• 更新モノイド、演算モノイド、作用素モノイド、更新区間、演算区間を指定することで適切な木の構造体を構築
  • 星空木、Fenwick木、セグ木、双対セグ木、遅延セグ木を自動選択
  • 1点でも区間でも、更新はupdate
  • 1点でも区間でも、取得はquery

計算量

• 構築: $O(N)$
• 更新update: $O(logN)$
• 取得query: $O(logN)$

使い方

// 更新:Add, 演算:Min, 範囲-範囲
UnifiedSegmentTree<Monoid::Min, Monoid::Add> seg(N, RangeType::Range, RangeType::Range);
seg.update(l, r, v);
int res = seg.query(l, r);

// 更新:Add, 演算:Add, 一点-範囲
UnifiedSegmentTree<Monoid::Add, Monoid::Add> seg(N, RangeType::Single, RangeType::Range);
seg.update(i, i+1, v);
int res = seg.query(l, r);

// 第3引数に作用素 Act を指定
UnifiedSegmentTree<Monoid::Add, Monoid::Set, MonoidAct::AddSet> seg(N, RangeType::Range, RangeType::Range);
seg.update(l, r, v);
int res = seg.query(l, r);

// 配列でも初期化できる
vector<int> A = {1, 2, 3, 4, 5};

// 例：一点更新・範囲最小値（SegmentTreeが自動選択される）
UnifiedSegmentTree<Monoid::Min> seg(A, RangeType::Single, RangeType::Range);

// 例：範囲加算・範囲最大値（StarrySkyTreeが自動選択される）
UnifiedSegmentTree<Monoid::Max, Monoid::Add> sst(A, RangeType::Range, RangeType::Range);

Depends on

• Dual Segment Tree (library/segtree/dual_segment_tree.hpp)
• Fenwick Tree (library/segtree/fenwick_tree.hpp)
• Lazy Segment Tree (library/segtree/lazy_segment_tree.hpp)
• Segment Tree (library/segtree/segment_tree.hpp)
• Starry Sky Tree (library/segtree/starry_sky_tree.hpp)
• モノイド (library/various/monoid.hpp)
• モノイド作用素 (library/various/monoid_act.hpp)

Verified with

• 統合セグ木のテスト:RMQ RAQ (tests/segtree.unified_segment_tree.test.cpp)

Code

#pragma once
#include <variant>
#include <type_traits>
#include <functional>
#include "library/segtree/dual_segment_tree.hpp"
#include "library/segtree/fenwick_tree.hpp"
#include "library/segtree/lazy_segment_tree.hpp"
#include "library/segtree/segment_tree.hpp"
#include "library/segtree/starry_sky_tree.hpp"
#include "library/various/monoid.hpp"
#include "library/various/monoid_act.hpp"
enum class RangeType { Single, Range };
template <typename ProdMonoid, typename UpdMonoid = ProdMonoid,
          typename Act = void>
struct UnifiedSegmentTree {
    // std::decay_t を使って const や参照を除去した純粋な型を取得する
    using T = std::decay_t<decltype(ProdMonoid::e)>;
    using U = std::decay_t<decltype(UpdMonoid::e)>;
    using VariantType =
        std::variant<std::monostate, SegmentTree<T>, DualSegmentTree<U>,
                     LazySegmentTree<T, U>, FenwickTree, StarrySkyTree<true>,
                     StarrySkyTree<false>>;

  private:
    VariantType tree;
    int N;
    // 分岐ロジック：upd_t, prod_t はコンパイル時に判定できないため、
    // if constexpr ではなく通常の if
    // で分岐させるか、テンプレート引数に移動させる必要があります。
    // 今回は使い勝手を優先し、実行時の if 分岐で variant に代入します。
    template <typename InitData>
    void construct(int n, const InitData &data, RangeType upd_t,
                   RangeType prod_t) {
        N = n;
        constexpr bool is_vec = !std::is_integral_v<InitData>;
        // 1. 星空木 (型判定のみなので if constexpr が使える)
        if constexpr (std::is_same_v<UpdMonoid, Monoid::Add> &&
                      std::is_same_v<ProdMonoid, Monoid::Min>) {
            if constexpr (is_vec)
                tree.template emplace<StarrySkyTree<true>>(data);
            else
                tree.template emplace<StarrySkyTree<true>>(N);
        } else if constexpr (std::is_same_v<UpdMonoid, Monoid::Add> &&
                             std::is_same_v<ProdMonoid, Monoid::Max>) {
            if constexpr (is_vec)
                tree.template emplace<StarrySkyTree<false>>(data);
            else
                tree.template emplace<StarrySkyTree<false>>(N);
        }
        // 2. Fenwick Tree (upd_t は実行時変数なので通常の if)
        else if (upd_t == RangeType::Single && prod_t == RangeType::Range &&
                 std::is_same_v<UpdMonoid, Monoid::Add> &&
                 std::is_same_v<ProdMonoid, Monoid::Add> &&
                 std::is_same_v<T, long long>) {
            // ユーザー環境に合わせて int/long long は調整が必要ですが、ここでは
            // A の型に合わせます
            if constexpr (is_vec)
                tree.template emplace<FenwickTree>(data);
            else
                tree.template emplace<FenwickTree>(N);
        }
        // 3. Segment Tree (Point Update / Range Product)
        else if (upd_t == RangeType::Single && prod_t == RangeType::Range) {
            if constexpr (is_vec)
                tree.template emplace<SegmentTree<T>>(ProdMonoid::op,
                                                      ProdMonoid::e, data);
            else
                tree.template emplace<SegmentTree<T>>(ProdMonoid::op,
                                                      ProdMonoid::e, N);
        }
        // 4. Dual Segment Tree (Range Update / Point Get)
        else if (upd_t == RangeType::Range && prod_t == RangeType::Single) {
            if constexpr (is_vec)
                tree.template emplace<DualSegmentTree<U>>(UpdMonoid::op,
                                                          UpdMonoid::e, data);
            else
                tree.template emplace<DualSegmentTree<U>>(UpdMonoid::op,
                                                          UpdMonoid::e, N);
        }
        // 5. Lazy Segment Tree
        else {
            static_assert(!std::is_void_v<Act>,
                          "LazySegmentTree requires an Act operator.");
            if constexpr (is_vec)
                tree.template emplace<LazySegmentTree<T, U>>(
                    ProdMonoid::op, ProdMonoid::e, UpdMonoid::op, UpdMonoid::e,
                    Act::op, data);
            else
                tree.template emplace<LazySegmentTree<T, U>>(
                    ProdMonoid::op, ProdMonoid::e, UpdMonoid::op, UpdMonoid::e,
                    Act::op, N);
        }
    }

  public:
    UnifiedSegmentTree(int n, RangeType upd_t, RangeType prod_t) {
        construct(n, n, upd_t, prod_t);
    }
    UnifiedSegmentTree(const std::vector<T> &a, RangeType upd_t,
                       RangeType prod_t) {
        construct(a.size(), a, upd_t, prod_t);
    }
    void update(int l, int r, U x) {
        std::visit(
            [&](auto &&t) {
                using VT = std::decay_t<decltype(t)>;
                if constexpr (std::is_same_v<VT, StarrySkyTree<true>> ||
                              std::is_same_v<VT, StarrySkyTree<false>> ||
                              std::is_same_v<VT, DualSegmentTree<U>> ||
                              std::is_same_v<VT, LazySegmentTree<T, U>>) {
                    t.apply(l, r, x);
                } else if constexpr (std::is_same_v<VT, SegmentTree<T>>) {
                    t.set(l, x);
                } else if constexpr (std::is_same_v<VT, FenwickTree>) {
                    t.add(l, x);
                }
            },
            tree);
    }
    T query(int l, int r) {
        return std::visit(
            [&](auto &&t) -> T {
                using VT = std::decay_t<decltype(t)>;
                if constexpr (std::is_same_v<VT, StarrySkyTree<true>> ||
                              std::is_same_v<VT, StarrySkyTree<false>> ||
                              std::is_same_v<VT, SegmentTree<T>> ||
                              std::is_same_v<VT, LazySegmentTree<T, U>>) {
                    return t.prod(l, r);
                } else if constexpr (std::is_same_v<VT, DualSegmentTree<U>>) {
                    return t[l];
                } else if constexpr (std::is_same_v<VT, FenwickTree>) {
                    return t.sum(r - 1) - t.sum(l - 1);
                }
                return (T)ProdMonoid::e;
            },
            tree);
    }
};

#line 2 "library/segtree/unified_segment_tree.hpp"
#include <variant>
#include <type_traits>
#include <functional>
#line 2 "library/various/monoid.hpp"
/**
 * @brief モノイド
 */
struct Monoid {
    // 最小値
    struct Min {
        static constexpr int e = INT_MAX;
        static int op(int x, int y) { return min(x, y); }
    };
    // 最大値
    struct Max {
        static constexpr int e = -INT_MAX;
        static int op(int x, int y) { return max(x, y); }
    };
    // 加算
    struct Add {
        static constexpr int e = 0;
        static int op(int x, int y) { return x + y; }
    };
    // 乗算
    struct Mul {
        static constexpr int e = 1;
        static int op(int x, int y) { return x * y; }
    };
    // 代入
    struct Set {
        static constexpr int e = INT_MAX;
        static int op(int x, int y) { return y == INT_MAX ? x : y; }
    };
    // 最大公約数
    struct Gcd {
        static constexpr int e = 0;
        static int op(int x, int y) { return gcd(x, y); }
    };
    // 最小公倍数
    struct Lcm {
        static constexpr int e = 1;
        static int op(int x, int y) { return lcm(x, y); }
    };
    // 排他的論理和
    struct Xor {
        static constexpr int e = 0;
        static int op(int x, int y) { return x ^ y; }
    };
};
#line 4 "library/segtree/dual_segment_tree.hpp"
template <typename T> struct DualSegmentTree {
    using F = function<T(T, T)>;

  private:
    F op;
    T e;
    int N, size, log = 1;
    vector<T> node;
    void init() {
        while ((1ll << log) < N) ++log;
        node.assign((size = 1ll << log) << 1, e);
    }
    void apply_at(int k, T a) { node[k] = op(node[k], a); }
    void propagate(int k) {
        if (node[k] == e) return;
        apply_at((k << 1 | 0), node[k]);
        apply_at((k << 1 | 1), node[k]);
        node[k] = e;
    }

  public:
    DualSegmentTree(F op, T e, int n) : op(op), e(e), N(n) { init(); }
    DualSegmentTree(F op, T e, const vector<T> &a) : op(op), e(e), N(a.size()) {
        init();
        for (int i = 0; i < N; ++i) node[i + size] = a[i];
    }
    T operator[](int p) {
        p += size;
        for (int i = log; i >= 1; --i) propagate(p >> i);
        return node[p];
    }
    void set(int p, const T &x) {
        p += size;
        apply_at(p, x);
        node[p] = x;
    }
    void apply(int l, int r, const T &a) {
        if (l == r) return;
        l += size, r += size;
        for (int i = log; i >= 1; --i) {
            if (((l >> i) << i) != l) propagate(l >> i);
            if (((r >> i) << i) != r) propagate((r - 1) >> i);
        }
        while (l < r) {
            if (l & 1) apply_at(l++, a);
            if (r & 1) apply_at(--r, a);
            l >>= 1, r >>= 1;
        }
    }
};
#line 2 "library/segtree/fenwick_tree.hpp"
struct FenwickTree {
  private:
    int N;
    vector<int> fwk;

  public:
    FenwickTree(int N) : N(N) { fwk.assign(N + 1, 0); }
    FenwickTree(const vector<int> &A) : N(A.size()) {
        fwk.assign(N + 1, 0);
        for (int i = 1; i <= N; ++i) {
            fwk[i] += A[i - 1];
            if (i + (i & -i) <= N) fwk[i + (i & -i)] += fwk[i];
        }
    }
    void add(int i, const int &x) {
        for (++i; i <= N; i += i & -i) fwk[i] += x;
    }
    int sum(int i) {
        int ans = 0;
        for (++i; i; i -= i & -i) ans += fwk[i];
        return ans;
    }
};
#line 3 "library/various/monoid_act.hpp"
/**
 * @brief モノイド作用素
 */
struct MonoidAct {
    // 演算: 加算  更新: 加算
    struct AddAdd {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            return node + a * size;
        }
    };
    // 演算: 加算  更新: 代入
    struct AddSet {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            return a == Monoid::Set::e ? node : a * size;
        }
    };
    // 演算: 加算  更新: 最小値
    struct AddMin {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return min(node, a);
        }
    };
    // 演算: 加算  更新: 最大値
    struct AddMax {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return max(node, a);
        }
    };
    // 演算: 最小値  更新: 加算
    struct MinAdd {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return node == Monoid::Min::e ? node : node + a;
        }
    };
    // 演算: 最小値  更新: 代入
    struct MinSet {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return a == Monoid::Set::e ? node : a;
        }
    };
    // 演算: 最小値  更新: 最小値
    struct MinMin {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return min(node, a);
        }
    };
    // 演算: 最小値  更新: 最大値
    struct MinMax {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return max(node, a);
        }
    };
    // 演算: 最大値  更新: 加算
    struct MaxAdd {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return node == Monoid::Max::e ? node : node + a;
        }
    };
    // 演算: 最大値  更新: 代入
    struct MaxSet {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return a == Monoid::Set::e ? node : a;
        }
    };
    // 演算: 最大値  更新: 最小値
    struct MaxMin {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return min(node, a);
        }
    };
    // 演算: 最大値  更新: 最大値
    struct MaxMax {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return max(node, a);
        }
    };
};
#line 5 "library/segtree/lazy_segment_tree.hpp"
template <typename T, typename U> struct LazySegmentTree {
    using ProdOp = function<T(T, T)>;
    using UpdOp = function<U(U, U)>;
    using ActOp = function<T(T, U, int)>;

  private:
    ProdOp prod_op;
    T prod_e;
    UpdOp upd_op;
    U upd_e;
    ActOp act_op;
    int N, size, log = 1;
    vector<T> node;
    vector<U> lazy;
    void init() {
        while ((1ll << log) < N) ++log;
        node.assign((size = 1ll << log) << 1, prod_e);
        lazy.assign(size, upd_e);
    }
    void update(int i) {
        node[i] = prod_op(node[i << 1 | 0], node[i << 1 | 1]);
    }
    void apply_at(int k, U a) {
        int topbit = k == 0 ? -1 : 31 - __builtin_clzll(k);
        long long sz = 1 << (log - topbit);
        node[k] = act_op(node[k], a, sz);
        if (k < size) lazy[k] = upd_op(lazy[k], a);
    }
    void propagate(int k) {
        if (lazy[k] == upd_e) return;
        apply_at((k << 1 | 0), lazy[k]);
        apply_at((k << 1 | 1), lazy[k]);
        lazy[k] = upd_e;
    }

  public:
    LazySegmentTree(ProdOp prod_op, T prod_e, UpdOp upd_op, U upd_e,
                    ActOp act_op, int n)
        : prod_op(prod_op), prod_e(prod_e), upd_op(upd_op), upd_e(upd_e),
          act_op(act_op), N(n) {
        init();
    }
    LazySegmentTree(ProdOp prod_op, T prod_e, UpdOp upd_op, U upd_e,
                    ActOp act_op, const vector<T> &a)
        : prod_op(prod_op), prod_e(prod_e), upd_op(upd_op), upd_e(upd_e),
          act_op(act_op), N(a.size()) {
        init();
        for (int i = 0; i < N; ++i) node[i + size] = a[i];
        for (int i = size - 1; i >= 1; --i) update(i);
    }
    T operator[](int p) {
        p += size;
        for (int i = log; i >= 1; --i) propagate(p >> i);
        return node[p];
    }
    vector<T> getall() {
        for (int i = 1; i < size; ++i) propagate(i);
        return {node.begin() + size, node.begin() + size + N};
    }
    void set(int p, const T &x) {
        p += size;
        for (int i = log; i >= 1; --i) propagate(p >> i);
        node[p] = x;
        for (int i = 1; i <= log; ++i) update(p >> i);
    }
    T prod(int l, int r) {
        if (l == r) return prod_e;
        l += size, r += size;
        for (int i = log; i >= 1; --i) {
            if (((l >> i) << i) != l) propagate(l >> i);
            if (((r >> i) << i) != r) propagate((r - 1) >> i);
        }
        T L = prod_e, R = prod_e;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) L = prod_op(L, node[l++]);
            if (r & 1) R = prod_op(node[--r], R);
        }
        return prod_op(L, R);
    }
    T top() { return node[1]; }
    void apply(int l, int r, U a) {
        if (l == r) return;
        l += size, r += size;
        for (int i = log; i >= 1; --i) {
            if (((l >> i) << i) != l) propagate(l >> i);
            if (((r >> i) << i) != r) propagate((r - 1) >> i);
        }
        int l2 = l, r2 = r;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) apply_at(l++, a);
            if (r & 1) apply_at(--r, a);
        }
        l = l2, r = r2;
        for (int i = 1; i <= log; ++i) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
    template <typename F> int max_right(const F &test, int L) {
        if (L == N) return N;
        L += size;
        for (int i = log; i >= 1; --i) propagate(L >> i);
        T sm = prod_e;
        do {
            while (L % 2 == 0) L >>= 1;
            if (!test(prod_op(sm, node[L]))) {
                while (L < size) {
                    propagate(L);
                    L = 2 * L;
                    if (test(prod_op(sm, node[L]))) sm = prod_op(sm, node[L++]);
                }
                return L - size;
            }
            sm = prod_op(sm, node[L++]);
        } while ((L & -L) != L);
        return N;
    }
    template <typename F> int min_left(const F test, int R) {
        if (R == 0) return 0;
        R += size;
        for (int i = log; i >= 1; i--) propagate((R - 1) >> i);
        T sm = prod_e;
        do {
            R--;
            while (R > 1 && (R % 2)) R >>= 1;
            if (!test(prod_op(node[R], sm))) {
                while (R < size) {
                    propagate(R);
                    R = 2 * R + 1;
                    if (test(prod_op(node[R], sm))) sm = prod_op(node[R--], sm);
                }
                return R + 1 - size;
            }
            sm = prod_op(node[R], sm);
        } while ((R & -R) != R);
        return 0;
    }
};
#line 4 "library/segtree/segment_tree.hpp"
template <typename T> struct SegmentTree {
    using F = function<T(T, T)>;

  private:
    F op;
    T e;
    int N, size, log = 1;
    vector<T> node;
    void init() {
        while ((1ll << log) < N) ++log;
        node.assign((size = 1ll << log) << 1, e);
    }

  public:
    SegmentTree(F op, T e, int N) : op(op), e(e), N(N) { init(); }
    SegmentTree(F op, T e, const vector<T> &A) : op(op), e(e), N(A.size()) {
        init();
        for (int i = 0; i < N; ++i) node[i + size] = A[i];
        for (int i = size - 1; i >= 1; --i)
            node[i] = op(node[i << 1 | 0], node[i << 1 | 1]);
    }
    void set(int i, const T &x) {
        node[i += size] = x;
        while (i >>= 1) node[i] = op(node[i << 1 | 0], node[i << 1 | 1]);
    }
    T prod(int l, int r) {
        T L = e, R = e;
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) L = op(L, node[l++]);
            if (r & 1) R = op(node[--r], R);
        }
        return op(L, R);
    }
};
#line 2 "library/segtree/starry_sky_tree.hpp"
template <bool is_min_mode = true> struct StarrySkyTree {
  private:
    int N, sz, log = 1;
    const int INF = 1e9;
    vector<int> node;
    int compare(int a, int b) {
        if constexpr (is_min_mode) {
            return min(a, b);
        } else {
            return max(a, b);
        }
    }
    int unit_element() { return is_min_mode ? INF : -INF; }
    void init() {
        while ((1ll << log) < N) ++log;
        node.assign((sz = 1ll << log) << 1, 0);
    }
    int _star(int i) {
        int val = compare(node[i << 1 | 0], node[i << 1 | 1]);
        node[i << 1 | 0] -= val;
        node[i << 1 | 1] -= val;
        return val;
    }
    void star(int i) { node[i] += _star(i); }
    int sum(int i) {
        int ans = node[i];
        while (i >>= 1) ans += node[i];
        return ans;
    }

  public:
    StarrySkyTree(int n) : N(n) { init(); }
    StarrySkyTree(const vector<int> &a) : N(a.size()) {
        init();
        for (int i = 0; i < N; ++i) node[i + sz] = a[i];
        for (int i = sz - 1; i >= 1; --i) node[i] = _star(i);
    }
    int operator[](int i) { return sum(i + sz); }
    void apply(int l, int r, const int &v) {
        if (l >= r) return;
        int l_bak = l + sz, r_bak = r + sz - 1;
        for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) node[l++] += v;
            if (r & 1) node[--r] += v;
        }
        for (int i = l_bak >> 1; i >= 1; i >>= 1) star(i);
        for (int i = r_bak >> 1; i >= 1; i >>= 1) star(i);
    }
    void set(int p, const int &x) { apply(p, p + 1, x - sum(p + sz)); }
    int prod(int l, int r) {
        if (l >= r) return unit_element();
        int ans = unit_element();
        for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ans = compare(ans, sum(l++));
            if (r & 1) ans = compare(ans, sum(--r));
        }
        return ans;
    }
};
#line 12 "library/segtree/unified_segment_tree.hpp"
enum class RangeType { Single, Range };
template <typename ProdMonoid, typename UpdMonoid = ProdMonoid,
          typename Act = void>
struct UnifiedSegmentTree {
    // std::decay_t を使って const や参照を除去した純粋な型を取得する
    using T = std::decay_t<decltype(ProdMonoid::e)>;
    using U = std::decay_t<decltype(UpdMonoid::e)>;
    using VariantType =
        std::variant<std::monostate, SegmentTree<T>, DualSegmentTree<U>,
                     LazySegmentTree<T, U>, FenwickTree, StarrySkyTree<true>,
                     StarrySkyTree<false>>;

  private:
    VariantType tree;
    int N;
    // 分岐ロジック：upd_t, prod_t はコンパイル時に判定できないため、
    // if constexpr ではなく通常の if
    // で分岐させるか、テンプレート引数に移動させる必要があります。
    // 今回は使い勝手を優先し、実行時の if 分岐で variant に代入します。
    template <typename InitData>
    void construct(int n, const InitData &data, RangeType upd_t,
                   RangeType prod_t) {
        N = n;
        constexpr bool is_vec = !std::is_integral_v<InitData>;
        // 1. 星空木 (型判定のみなので if constexpr が使える)
        if constexpr (std::is_same_v<UpdMonoid, Monoid::Add> &&
                      std::is_same_v<ProdMonoid, Monoid::Min>) {
            if constexpr (is_vec)
                tree.template emplace<StarrySkyTree<true>>(data);
            else
                tree.template emplace<StarrySkyTree<true>>(N);
        } else if constexpr (std::is_same_v<UpdMonoid, Monoid::Add> &&
                             std::is_same_v<ProdMonoid, Monoid::Max>) {
            if constexpr (is_vec)
                tree.template emplace<StarrySkyTree<false>>(data);
            else
                tree.template emplace<StarrySkyTree<false>>(N);
        }
        // 2. Fenwick Tree (upd_t は実行時変数なので通常の if)
        else if (upd_t == RangeType::Single && prod_t == RangeType::Range &&
                 std::is_same_v<UpdMonoid, Monoid::Add> &&
                 std::is_same_v<ProdMonoid, Monoid::Add> &&
                 std::is_same_v<T, long long>) {
            // ユーザー環境に合わせて int/long long は調整が必要ですが、ここでは
            // A の型に合わせます
            if constexpr (is_vec)
                tree.template emplace<FenwickTree>(data);
            else
                tree.template emplace<FenwickTree>(N);
        }
        // 3. Segment Tree (Point Update / Range Product)
        else if (upd_t == RangeType::Single && prod_t == RangeType::Range) {
            if constexpr (is_vec)
                tree.template emplace<SegmentTree<T>>(ProdMonoid::op,
                                                      ProdMonoid::e, data);
            else
                tree.template emplace<SegmentTree<T>>(ProdMonoid::op,
                                                      ProdMonoid::e, N);
        }
        // 4. Dual Segment Tree (Range Update / Point Get)
        else if (upd_t == RangeType::Range && prod_t == RangeType::Single) {
            if constexpr (is_vec)
                tree.template emplace<DualSegmentTree<U>>(UpdMonoid::op,
                                                          UpdMonoid::e, data);
            else
                tree.template emplace<DualSegmentTree<U>>(UpdMonoid::op,
                                                          UpdMonoid::e, N);
        }
        // 5. Lazy Segment Tree
        else {
            static_assert(!std::is_void_v<Act>,
                          "LazySegmentTree requires an Act operator.");
            if constexpr (is_vec)
                tree.template emplace<LazySegmentTree<T, U>>(
                    ProdMonoid::op, ProdMonoid::e, UpdMonoid::op, UpdMonoid::e,
                    Act::op, data);
            else
                tree.template emplace<LazySegmentTree<T, U>>(
                    ProdMonoid::op, ProdMonoid::e, UpdMonoid::op, UpdMonoid::e,
                    Act::op, N);
        }
    }

  public:
    UnifiedSegmentTree(int n, RangeType upd_t, RangeType prod_t) {
        construct(n, n, upd_t, prod_t);
    }
    UnifiedSegmentTree(const std::vector<T> &a, RangeType upd_t,
                       RangeType prod_t) {
        construct(a.size(), a, upd_t, prod_t);
    }
    void update(int l, int r, U x) {
        std::visit(
            [&](auto &&t) {
                using VT = std::decay_t<decltype(t)>;
                if constexpr (std::is_same_v<VT, StarrySkyTree<true>> ||
                              std::is_same_v<VT, StarrySkyTree<false>> ||
                              std::is_same_v<VT, DualSegmentTree<U>> ||
                              std::is_same_v<VT, LazySegmentTree<T, U>>) {
                    t.apply(l, r, x);
                } else if constexpr (std::is_same_v<VT, SegmentTree<T>>) {
                    t.set(l, x);
                } else if constexpr (std::is_same_v<VT, FenwickTree>) {
                    t.add(l, x);
                }
            },
            tree);
    }
    T query(int l, int r) {
        return std::visit(
            [&](auto &&t) -> T {
                using VT = std::decay_t<decltype(t)>;
                if constexpr (std::is_same_v<VT, StarrySkyTree<true>> ||
                              std::is_same_v<VT, StarrySkyTree<false>> ||
                              std::is_same_v<VT, SegmentTree<T>> ||
                              std::is_same_v<VT, LazySegmentTree<T, U>>) {
                    return t.prod(l, r);
                } else if constexpr (std::is_same_v<VT, DualSegmentTree<U>>) {
                    return t[l];
                } else if constexpr (std::is_same_v<VT, FenwickTree>) {
                    return t.sum(r - 1) - t.sum(l - 1);
                }
                return (T)ProdMonoid::e;
            },
            tree);
    }
};

Back to top page