Dual Segment Tree
(library/segtree/dual_segment_tree.hpp)

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

Dual Segment Tree

できること

• モノイドについて処理
• 区間[l, r)の値を更新
• 1点の演算結果を取得

計算量

• 構築: $O(N)$
• 1点取得seg[i]: $O(logN)$
• 1点更新set: $O(logN)$
• 区間更新apply: $O(logN)$

使い方

DualSegmentTree<int> seg(Monoid::Min::op, Monoid::Min::e, N);

Depends on

• モノイド (library/various/monoid.hpp)

Required by

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

Verified with

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

Code

#pragma once
#include <functional>
#include "library/various/monoid.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/dual_segment_tree.hpp"
#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;
        }
    }
};

Back to top page