DynamicSegmentTree - 非再帰抽象化動的セグメント木
(lib/10-segment-tree/DynamicSegmentTree.cpp)

• View this file on GitHub
• Last update: 2023-07-02 23:40:36+09:00

DynamicSegmentTree

• 非再帰抽象化動的セグメント木
• ポインタベースで、必要な部分だけ作成するセグメント木
  • 普通のセグ木と違って、区間の幅を1e9で持ったり出来る
• 0-indexed
• モノイドのクラスをテンプレートで渡す必要がある
  • 下記が一例

    //一点加算 区間総和
    template<class T> struct NodeSumPointAdd {
    using TypeNode = T;
    inline static constexpr TypeNode unit_node = 0;
    inline static constexpr TypeNode func_node(TypeNode l,TypeNode r){return l+r;}
    inline static constexpr TypeNode func_merge(TypeNode l,TypeNode r){return l+r;}
    };
    

• モノイドのクラスは、get,updateに対する演算と単位元を必要とする。

コンストラクタ

• DynamicSegmentTree()
  • 単位元unit_nodeで初期化

メソッド

• void operate(size_t idx, const TypeNode var)
  • idx番目のデータに値varを作用させる
  • $O(logN)$
  • idx:添字 0-indexed
  • var:値
  • 更新や加算などが乗る
• TypeNode fold(int l, int r)
  • 半開区間[l,r)をfoldした値を返す
  • $O(logN)$
  • l,r:添字 0-indexed
  • 総和や最大などが乗る
• void print()
  • デバッグ用

Verified with

• test/segment-tree/DynamicSegmentTree-rcq-1.test.cpp
• test/segment-tree/DynamicSegmentTree-rsq-1.test.cpp
• test/segment-tree/DynamicSegmentTree-rsq-2.test.cpp
• test/segment-tree/DynamicSegmentTree-rsq-3.test.cpp

Code

/*
 * @title DynamicSegmentTree - 非再帰抽象化動的セグメント木
 * @docs md/segment-tree/DynamicSegmentTree.md
 */
template<class Monoid> class DynamicSegmentTree {
    using TypeNode = typename Monoid::TypeNode;
    using i64 = long long;

    struct Node{
        Node *left, *right;
        TypeNode val;
        Node():left(nullptr),right(nullptr),val(Monoid::unit_node) {}
    };

    TypeNode dfs(i64 l,i64 r,i64 nl,i64 nr,Node* node) {
        if(l <= nl && nr <= r) return node->val;
        if(nr <= l || r <= nl) return Monoid::unit_node;
        TypeNode vl=Monoid::unit_node, vr=Monoid::unit_node;
        i64 m = (nl+nr)>>1;
        if(node->left)  vl = dfs(l,r,nl,m,node->left);
        if(node->right) vr = dfs(l,r,m,nr,node->right);
        return Monoid::func_fold(vl,vr);
    }

    i64 length;
    Node *root;
public:
    //unitで初期化
    DynamicSegmentTree() : length(1) {
        root = new Node();
    }
    //[idx,idx+1)
    void operate(i64 idx, const TypeNode val) {
        if(idx < 0) return;
        for (;length <= idx; length *= 2) {
            Node *new_root = new Node();
            TypeNode val = root->val;
            new_root->left = root;
            root = new_root;
            root->val = val;
        }
        Node* node = root;
        i64 l = 0, r = length, m;
		stack<Node*> st;

        while(r-l>1) {
			st.push(node);
            m = (r+l)>>1;
            if(idx<m) {
                r = m;
                if(!node->left) node->left=new Node();
                node = node->left;
            }
            else {
                l = m;
                if(!node->right) node->right = new Node();
                node = node->right;
            }
        }
        node->val = Monoid::func_operate(node->val,val);
		while(st.size()) {
			node = st.top(); st.pop();
			TypeNode vl=Monoid::unit_node, vr=Monoid::unit_node;
			if(node->left)  vl = node->left->val;
			if(node->right) vr = node->right->val;
			node->val = Monoid::func_fold(vl,vr);
		}
    }

    //[l,r)
    TypeNode fold(i64 l, i64 r) {
        if (l < 0 || length <= l || r < 0) return Monoid::unit_node;
        return dfs(l,r,0,length,root);
    }
};

#line 1 "lib/10-segment-tree/DynamicSegmentTree.cpp"
/*
 * @title DynamicSegmentTree - 非再帰抽象化動的セグメント木
 * @docs md/segment-tree/DynamicSegmentTree.md
 */
template<class Monoid> class DynamicSegmentTree {
    using TypeNode = typename Monoid::TypeNode;
    using i64 = long long;

    struct Node{
        Node *left, *right;
        TypeNode val;
        Node():left(nullptr),right(nullptr),val(Monoid::unit_node) {}
    };

    TypeNode dfs(i64 l,i64 r,i64 nl,i64 nr,Node* node) {
        if(l <= nl && nr <= r) return node->val;
        if(nr <= l || r <= nl) return Monoid::unit_node;
        TypeNode vl=Monoid::unit_node, vr=Monoid::unit_node;
        i64 m = (nl+nr)>>1;
        if(node->left)  vl = dfs(l,r,nl,m,node->left);
        if(node->right) vr = dfs(l,r,m,nr,node->right);
        return Monoid::func_fold(vl,vr);
    }

    i64 length;
    Node *root;
public:
    //unitで初期化
    DynamicSegmentTree() : length(1) {
        root = new Node();
    }
    //[idx,idx+1)
    void operate(i64 idx, const TypeNode val) {
        if(idx < 0) return;
        for (;length <= idx; length *= 2) {
            Node *new_root = new Node();
            TypeNode val = root->val;
            new_root->left = root;
            root = new_root;
            root->val = val;
        }
        Node* node = root;
        i64 l = 0, r = length, m;
		stack<Node*> st;

        while(r-l>1) {
			st.push(node);
            m = (r+l)>>1;
            if(idx<m) {
                r = m;
                if(!node->left) node->left=new Node();
                node = node->left;
            }
            else {
                l = m;
                if(!node->right) node->right = new Node();
                node = node->right;
            }
        }
        node->val = Monoid::func_operate(node->val,val);
		while(st.size()) {
			node = st.top(); st.pop();
			TypeNode vl=Monoid::unit_node, vr=Monoid::unit_node;
			if(node->left)  vl = node->left->val;
			if(node->right) vr = node->right->val;
			node->val = Monoid::func_fold(vl,vr);
		}
    }

    //[l,r)
    TypeNode fold(i64 l, i64 r) {
        if (l < 0 || length <= l || r < 0) return Monoid::unit_node;
        return dfs(l,r,0,length,root);
    }
};

Back to top page