Dynamic Segment Tree
(datastructure/segmenttree/dynamic_segtree.cpp)

View this file on GitHub
Last update: 2026-03-23 22:54:37+09:00

説明

必要なノードだけ作る動的セグメント木。大きい座標範囲に対する 1 点更新と区間積を扱う。各操作は生成ノード数に応じて $O(log N)$。

できること

DynamicSegmentTree<M> seg(n) 長さ n、初期値がすべて M::e() の動的セグメント木を作る
void reserve(size_t sz) ノード配列を sz 個ぶん予約する
void update(long long k, T x) 位置 k を x に置き換える
void add(long long k, T x) 位置 k を M::f(old, x) で更新する
T query(long long l, long long r) 半開区間 [l, r) の積を返す。空区間なら M::e()
T get(long long k) 位置 k の値を返す
T operator[](long long k) get(k) の短縮形

使い方

M に using T、static T f(T, T)、static T e() を定義して使う。

struct Monoid {
    using T = long long;
    static T f(T a, T b) { return a + b; }
    static T e() { return 0; }
};

DynamicSegmentTree<Monoid> seg((long long)1e9);
seg.add(123456789, 5);
seg.update(987654321, 7);
long long ans = seg.query(100000000, 900000000);

実装上の補足

未生成ノードは単位元として扱う。大量の更新を先に見積もれるときは reserve() で再確保を減らせる。この実装は初期配列をまとめて与える構築は持たず、必要な位置だけ更新して使う。

Verified with

test/yosupo_point_add_range_sum_dynamic_segtree.test.cpp

Code

template <class M>
struct DynamicSegmentTree{
    using T = typename M::T;
    struct Node{
        T val;
        int l, r;
    };

    long long n{};
    vector<Node> node;
    int root;

    explicit DynamicSegmentTree(long long n): n(n), root(-1) {}

    void reserve(size_t sz){
        node.reserve(sz);
    }

    void update(long long k, const T &x){
        if(n == 0) return;
        update_(root, k, x, 0, n);
    }

    void add(long long k, const T &x){
        if(n == 0) return;
        add_(root, k, x, 0, n);
    }

    T query(long long a, long long b) const {
        if(n == 0 || b <= a) return M::e();
        return query_(root, a, b, 0, n);
    }

    T get(long long k) const { return query(k, k+1); }
    T operator[](const long long &k) const { return get(k); }

private:
    int make_node(const T &v, int l, int r){
        node.push_back({v, l, r});
        return (int)node.size()-1;
    }

    void update_(int &id, long long k, const T &x, long long l, long long r){
        if(id == -1) id = make_node(M::e(), -1, -1);
        if(l+1 == r){
            node[id].val = x;
            return;
        }
        long long m = l + ((r-l)>>1);
        if(k < m){
            int child = node[id].l;
            update_(child, k, x, l, m);
            node[id].l = child;
        }else{
            int child = node[id].r;
            update_(child, k, x, m, r);
            node[id].r = child;
        }
        node[id].val = M::f(value(node[id].l), value(node[id].r));
    }

    void add_(int &id, long long k, const T &x, long long l, long long r){
        if(id == -1) id = make_node(M::e(), -1, -1);
        if(l+1 == r){
            node[id].val = M::f(node[id].val, x);
            return;
        }
        long long m = l + ((r-l)>>1);
        if(k < m){
            int child = node[id].l;
            add_(child, k, x, l, m);
            node[id].l = child;
        }else{
            int child = node[id].r;
            add_(child, k, x, m, r);
            node[id].r = child;
        }
        node[id].val = M::f(value(node[id].l), value(node[id].r));
    }

    T query_(int id, long long a, long long b, long long l, long long r) const {
        if(id == -1 || r <= a || b <= l) return M::e();
        if(a <= l && r <= b) return node[id].val;
        long long m = l + ((r-l)>>1);
        return M::f(query_(node[id].l, a, b, l, m), query_(node[id].r, a, b, m, r));
    }

    T value(int id) const {
        return id == -1 ? M::e() : node[id].val;
    }
};

/*
struct Monoid{
    using T = long long;
    static T f(T a, T b) { return a + b; }
    static T e() { return 0; }
};
*/

/**
 * @brief Dynamic Segment Tree
 */

#line 1 "datastructure/segmenttree/dynamic_segtree.cpp"
template <class M>
struct DynamicSegmentTree{
    using T = typename M::T;
    struct Node{
        T val;
        int l, r;
    };

    long long n{};
    vector<Node> node;
    int root;

    explicit DynamicSegmentTree(long long n): n(n), root(-1) {}

    void reserve(size_t sz){
        node.reserve(sz);
    }

    void update(long long k, const T &x){
        if(n == 0) return;
        update_(root, k, x, 0, n);
    }

    void add(long long k, const T &x){
        if(n == 0) return;
        add_(root, k, x, 0, n);
    }

    T query(long long a, long long b) const {
        if(n == 0 || b <= a) return M::e();
        return query_(root, a, b, 0, n);
    }

    T get(long long k) const { return query(k, k+1); }
    T operator[](const long long &k) const { return get(k); }

private:
    int make_node(const T &v, int l, int r){
        node.push_back({v, l, r});
        return (int)node.size()-1;
    }

    void update_(int &id, long long k, const T &x, long long l, long long r){
        if(id == -1) id = make_node(M::e(), -1, -1);
        if(l+1 == r){
            node[id].val = x;
            return;
        }
        long long m = l + ((r-l)>>1);
        if(k < m){
            int child = node[id].l;
            update_(child, k, x, l, m);
            node[id].l = child;
        }else{
            int child = node[id].r;
            update_(child, k, x, m, r);
            node[id].r = child;
        }
        node[id].val = M::f(value(node[id].l), value(node[id].r));
    }

    void add_(int &id, long long k, const T &x, long long l, long long r){
        if(id == -1) id = make_node(M::e(), -1, -1);
        if(l+1 == r){
            node[id].val = M::f(node[id].val, x);
            return;
        }
        long long m = l + ((r-l)>>1);
        if(k < m){
            int child = node[id].l;
            add_(child, k, x, l, m);
            node[id].l = child;
        }else{
            int child = node[id].r;
            add_(child, k, x, m, r);
            node[id].r = child;
        }
        node[id].val = M::f(value(node[id].l), value(node[id].r));
    }

    T query_(int id, long long a, long long b, long long l, long long r) const {
        if(id == -1 || r <= a || b <= l) return M::e();
        if(a <= l && r <= b) return node[id].val;
        long long m = l + ((r-l)>>1);
        return M::f(query_(node[id].l, a, b, l, m), query_(node[id].r, a, b, m, r));
    }

    T value(int id) const {
        return id == -1 ? M::e() : node[id].val;
    }
};

/*
struct Monoid{
    using T = long long;
    static T f(T a, T b) { return a + b; }
    static T e() { return 0; }
};
*/

/**
 * @brief Dynamic Segment Tree
 */

Dynamic Segment Tree (datastructure/segmenttree/dynamic_segtree.cpp)

説明

できること

使い方

実装上の補足

Verified with

Code

Dynamic Segment Tree
(datastructure/segmenttree/dynamic_segtree.cpp)