Dynamic Segment Tree (動的セグメント木)
(segment_tree/dynamic_segment_tree.hpp)

• View this file on GitHub
• Last update: 2026-04-13 20:18:41+09:00
• Include: #include "segment_tree/dynamic_segment_tree.hpp"

「必要な部分だけ作るセグメント木」と呼ばれるデータ構造です。

単位元 $e$ で初期化されている長さ $n$ の配列 $a$ に対し

• 要素の $1$ 点変更
• 区間の要素の総積の取得

を $O(\log n)$ 時間で処理することが出来ます。

このとき、$n$ は $10^9$ くらいでも処理することが出来ます。

テンプレート引数として、モノイド $(S, \cdot)$ を M として受け取ります。 モノイドとは以下の条件を満たす代数構造です。

• 結合律（ $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ ）が成立する。
• 単位元（ $a \cdot e=e \cdot a=a$ となる $e$ ）が存在する。

例えば、$\cdot$ として $\max$ を計算するモノイドは ここ に定義されています。

計算量は $\cdot$, $e$ が定数時間で計算できると仮定したときのものを記述します。

コンストラクタ

DynamicSegmentTree<M> seg(int n)

長さ $n$ の数列 $a$ を作ります。初期値は全部 $e$ です。

計算量

• $O(1)$

set

void seg.set(int p, S x)

$a_p$ に $x$ を代入します。

制約

• $0 \leq p < n$

計算量

• $O(\log n)$

add

void seg.add(int p, S x)

$a_p$ に $a_p \cdot x$ を代入します。

制約

• $0 \leq p < n$

計算量

• $O(\log n)$

get

(1) S seg.get(int p)
(2) S seg[int p]

$a_p$ を返します。

制約

• $0 \leq p < n$

計算量

• $O(\log n)$

prod

S seg.prod(int l, int r)

$a_l \cdot … \cdot a_{r - 1}$ を、モノイドの性質を満たしていると仮定して計算します。 $l = r$ のときは $e$ を返します。

制約

• $0 \leq l \leq r \leq n$

計算量

• $O(\log n)$

all_prod

S seg.all_prod()

$a_0 \cdot …\cdot a_{n - 1}$ を計算します。 $n = 0$ のときは $e$ を返します。

計算量

• $O(1)$

make_vector

std::vector<std::pair<int, S>> seg.make_vector()

現在の数列 $a$ のうち、一度でも set・add された $a_i$ に対する $(i, a_i)$ のペアを昇順に並べたものを返します。

計算量

一度でも set・add された $a_i$ の要素数を $q$ として

• $O(q \log n)$

Verified with

• segment_tree/test/dynamic_segment_tree.test.cpp

Code

#pragma once

#include <cassert>
#include <vector>

// Dynamic Segment Tree
// Q log_2(N) は Q = 500000, N = 10^18 のとき 30000000 くらい
template <class MS, int MAX_NODES = 30'000'000> struct DynamicSegmentTree {
  public:
    using S = typename MS::value_type;

    struct Node {
        S d;
        Node *l, *r;
        Node() = default;
        Node(S v, Node* l = nullptr, Node* r = nullptr) : d(v), l(l), r(r) {}
    };

    DynamicSegmentTree() = default;

    explicit DynamicSegmentTree(int n) : n(n), root(nullptr) {}

    void set(int p, const S& x) {
        assert(0 <= p and p < n);
        set(p, x, 0, n, root);
    }

    void add(int p, const S& x) {
        assert(0 <= p and p < n);
        add(p, x, 0, n, root);
    }

    S operator[](int p) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1);
    }

    S get(int p) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1);
    }

    S prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        return prod(l, r, 0, n, root);
    }

    S all_prod() const { return (root == nullptr ? MS::identity() : root->d); }

    std::vector<std::pair<int, S>> make_vector() const {
        std::vector<std::pair<int, S>> vec;
        auto rec = [&](auto f, int l, int r, Node* np) -> void {
            if (np == nullptr) return;
            if (l + 1 == r) vec.push_back({l, np->d});
            int m = (l + r) / 2;
            f(f, l, m, np->l);
            f(f, m, r, np->r);
        };
        rec(rec, 0, n, root);
        return vec;
    }

  private:
    int n;
    Node* root;
    static inline Node pool[MAX_NODES];
    static inline int pool_idx = 0;

    Node* new_node(S v, Node* l = nullptr, Node* r = nullptr) {
        return &(pool[pool_idx++] = Node(v, l, r));
    }

    Node* merge(Node* l, Node* r, Node* np) {
        np->d = MS::operation((l == nullptr ? MS::identity() : l->d),
                              (r == nullptr ? MS::identity() : r->d));
        return np;
    }

    Node* set(int p, const S& x, int l, int r, Node*& np) {
        if (np == nullptr) {
            np = new_node(MS::identity());
        }
        if (l + 1 == r) {
            np->d = x;
            return np;
        }
        int m = (l + r) / 2;
        if (l <= p and p < m) {
            return merge(set(p, x, l, m, np->l), np->r, np);
        } else {
            return merge(np->l, set(p, x, m, r, np->r), np);
        }
    }

    Node* add(int p, const S& x, int l, int r, Node*& np) {
        if (np == nullptr) {
            np = new_node(MS::identity());
        }
        if (l + 1 == r) {
            np->d = MS::operation(np->d, x);
            return np;
        }
        int m = (l + r) / 2;
        if (l <= p and p < m) {
            return merge(add(p, x, l, m, np->l), np->r, np);
        } else {
            return merge(np->l, add(p, x, m, r, np->r), np);
        }
    }

    S prod(int ql, int qr, int l, int r, Node* np) const {
        if (np == nullptr) return MS::identity();
        //  [ql, qr) と [l, r) が交差しない
        if (qr <= l or r <= ql) return MS::identity();
        // [ql, qr) が [l, r) を完全に含んでいる
        if (ql <= l and r <= qr) return np->d;
        int m = (l + r) / 2;
        return MS::operation(prod(ql, qr, l, m, np->l),
                             prod(ql, qr, m, r, np->r));
    }
};

#line 2 "segment_tree/dynamic_segment_tree.hpp"

#include <cassert>
#include <vector>

// Dynamic Segment Tree
// Q log_2(N) は Q = 500000, N = 10^18 のとき 30000000 くらい
template <class MS, int MAX_NODES = 30'000'000> struct DynamicSegmentTree {
  public:
    using S = typename MS::value_type;

    struct Node {
        S d;
        Node *l, *r;
        Node() = default;
        Node(S v, Node* l = nullptr, Node* r = nullptr) : d(v), l(l), r(r) {}
    };

    DynamicSegmentTree() = default;

    explicit DynamicSegmentTree(int n) : n(n), root(nullptr) {}

    void set(int p, const S& x) {
        assert(0 <= p and p < n);
        set(p, x, 0, n, root);
    }

    void add(int p, const S& x) {
        assert(0 <= p and p < n);
        add(p, x, 0, n, root);
    }

    S operator[](int p) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1);
    }

    S get(int p) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1);
    }

    S prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        return prod(l, r, 0, n, root);
    }

    S all_prod() const { return (root == nullptr ? MS::identity() : root->d); }

    std::vector<std::pair<int, S>> make_vector() const {
        std::vector<std::pair<int, S>> vec;
        auto rec = [&](auto f, int l, int r, Node* np) -> void {
            if (np == nullptr) return;
            if (l + 1 == r) vec.push_back({l, np->d});
            int m = (l + r) / 2;
            f(f, l, m, np->l);
            f(f, m, r, np->r);
        };
        rec(rec, 0, n, root);
        return vec;
    }

  private:
    int n;
    Node* root;
    static inline Node pool[MAX_NODES];
    static inline int pool_idx = 0;

    Node* new_node(S v, Node* l = nullptr, Node* r = nullptr) {
        return &(pool[pool_idx++] = Node(v, l, r));
    }

    Node* merge(Node* l, Node* r, Node* np) {
        np->d = MS::operation((l == nullptr ? MS::identity() : l->d),
                              (r == nullptr ? MS::identity() : r->d));
        return np;
    }

    Node* set(int p, const S& x, int l, int r, Node*& np) {
        if (np == nullptr) {
            np = new_node(MS::identity());
        }
        if (l + 1 == r) {
            np->d = x;
            return np;
        }
        int m = (l + r) / 2;
        if (l <= p and p < m) {
            return merge(set(p, x, l, m, np->l), np->r, np);
        } else {
            return merge(np->l, set(p, x, m, r, np->r), np);
        }
    }

    Node* add(int p, const S& x, int l, int r, Node*& np) {
        if (np == nullptr) {
            np = new_node(MS::identity());
        }
        if (l + 1 == r) {
            np->d = MS::operation(np->d, x);
            return np;
        }
        int m = (l + r) / 2;
        if (l <= p and p < m) {
            return merge(add(p, x, l, m, np->l), np->r, np);
        } else {
            return merge(np->l, add(p, x, m, r, np->r), np);
        }
    }

    S prod(int ql, int qr, int l, int r, Node* np) const {
        if (np == nullptr) return MS::identity();
        //  [ql, qr) と [l, r) が交差しない
        if (qr <= l or r <= ql) return MS::identity();
        // [ql, qr) が [l, r) を完全に含んでいる
        if (ql <= l and r <= qr) return np->d;
        int m = (l + r) / 2;
        return MS::operation(prod(ql, qr, l, m, np->l),
                             prod(ql, qr, m, r, np->r));
    }
};

Back to top page