Algoogle

Algorithm for Programming Contest

赤黒木(marge/split)

基本情報


計算量  
merge
split
insert
erase
add
minimum
空間

N := 要素数

解説


赤黒木をmerge/splitベースで書いたもの.
こっちの方がinsert/deleteベースより考えること(場合分け)が少ない.
赤黒木については赤黒木(insert/delete)を参照のこと
基本的に葉が各要素に対応している.
遅延評価を用いることで区間に値を足す操作を程度で行える.
できること

  • merge: 2つの木のマージ(順番を維持したまま)
  • split: 木をk番目で分割(左の木にk個の要素が入る)
  • insert: k番目に値valのノードもしくは木vを挿入する
  • erase: k番目の葉を削除する
  • add: 区間[l,r)に値valを一様に足す
  • minimum: 区間[l,r)の最小値

コード


(rbtree_merge.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
template<class T> class rbtree {
    enum COL { BLACK, RED, };
    struct node {
        T val, lazy, min_val;
        int color, rnk, size;
        node *left, *right;
        // if !left then this node is leaf
        node(){}
        node(T v) : val(v), min_val(v), color(BLACK), rnk(0), size(1) {
            left = right = NULL;
        }
        node(node *l, node *r, int c) : color(c) {
            left = l;
            right = r;
            update();
        }
        void update() {
            if(left) {
                rnk = max(left->rnk+(left->color==BLACK),
                          right->rnk+(right->color==BLACK));
                size = left->size+right->size;
                min_val = min(left->min_val, right->min_val);
            }
        }
    };

    node *new_node(T v) { return new node(v); }
    node *new_node(node *l, node *r, int c) { return new node(l,r,c); }
    node *rotate(node *v, int d) {
        node *w = d? v->right: v->left;
        if(d) {
            v->right = w->left;
            w->left = v;
            v->right->update();
        }
        else {
            v->left = w->right;
            w->right = v;
            v->left->update();
        }
        v->update(); w->update();
        v->color = RED;
        w->color = BLACK;
        return w;
    }
    node *merge_sub(node *u, node *v) {
        if(u->rnk < v->rnk) {
            node *w = merge_sub(u,v->left);
            v->left = w;
            v->update();
            if(v->color == BLACK and w->color == RED and w->left->color == RED) {
                if(v->right->color == BLACK)  return rotate(v,0);
                else {
                    v->color = RED;
                    v->left->color = v->right->color = BLACK;
                    return v;
                }
            }
            else return v;
        }
        else if(u->rnk > v->rnk) {
            node *w = merge_sub(u->right,v);
            u->right = w;
            u->update();
            if(u->color == BLACK and w->color == RED and w->right->color == RED) {
                if(u->left->color == BLACK) return rotate(u,1);
                else {
                    u->color = RED;
                    u->left->color = u->right->color = BLACK;
                    return u;
                }
            }
            else return u;
        }
        else return new_node(u,v,RED);
    }
    node *insert(node *v, int k) {
        auto p = split(root,k);
        return root = merge(merge(p.first,v),p.second);
    }
    T get(node *v, int k) {
        if(!v->left) return v->val;
        if(v->left->size > k) return get(v->left, k);
        return get(v->right, k-v->left->size);
    }
    T minimum(node *v, int l, int r) {
        if(r-l < 1) return inf;
        if(v->size == r-l) return v->min_val;
        return min(minimum(v->left, l, min(r, v->left->size)),
                   minimum(v->right, l-min(l, v->left->size), r-v->left->size));
    }
    T inf;
public:

    node *root;
    rbtree() {
        inf = (((1LL<<(sizeof(T)*8-2))-1)<<1)+1;
        root = NULL;
    }
    void clear() { root = NULL; }
    node *build(const vector<T> &vs) {
        if(!vs.size()) return root = NULL;
        if((int)vs.size() == 1) return root = new_node(vs[0]);
        int m = vs.size()/2;
        return root = merge(build(vector<T>(begin(vs),begin(vs)+m)), build(vector<T>(begin(vs)+m,end(vs))));
    }
    int size() { return root? root->size: 0; }
    node *push_back(T val) { return root = merge(root,new_node(val)); }
    node *push_front(T val) { return root = merge(new_node(val),root); }
    node *merge(node *u, node *v) {
        if(!u) return v;
        if(!v) return u;
        u = merge_sub(u,v);
        u->color = BLACK;
        return u;
    }
    pair<node*,node*> split(node *v, int k) {
        if(!k) return pair<node*,node*>(NULL,v);
        if(k == v->size) return pair<node*,node*>(v,NULL);
        if(k < v->left->size) {
            auto p = split(v->left,k);
            return pair<node*,node*>(p.first,merge(p.second,v->right));
        }
        else if(k > v->left->size) {
            auto p = split(v->right,k-v->left->size);
            return pair<node*,node*>(merge(v->left,p.first),p.second);
        }
        else return pair<node*,node*>(v->left,v->right);
    }

    node *insert(int k, T val) { return insert(new_node(val),k); }
    node *erase(int k) {
        auto p = split(root,k+1);
        return root = merge(split(p.first,k).first, p.second);
    }
    T get(int k) { return get(root, k); }
    T minimum(int l, int r) { return minimum(root, l, r); }
    T operator[](const int &i) { return get(i); }
};

Comments