persistent array

ソースコード

  1#include <vector>
  2using namespace std;
  3
  4// PersistentArray
  5namespace titan23 {
  6
  7    /**
  8     * @brief 永続配列
  9     */
 10    template<typename T>
 11    class PersistentArray {
 12      private:
 13        struct Node;
 14        using NodePtr = Node*;
 15
 16        NodePtr root;
 17        int n;
 18
 19        struct Node {
 20            T key;
 21            NodePtr left, right;
 22
 23            Node() : left(nullptr), right(nullptr) {}
 24            Node(T key) : key(key), left(nullptr), right(nullptr) {}
 25
 26            NodePtr copy() {
 27                NodePtr node = new Node(this->key);
 28                node->left = this->left;
 29                node->right = this->right;
 30                return node;
 31            }
 32        };
 33
 34        int bit_length(const int n) const {
 35            return n == 0 ? 0 : 32 - __builtin_clz(n);
 36        }
 37
 38        void _build(const vector<T> &a) {
 39            int n = a.size();
 40            this->n = n;
 41            if (n == 0) {
 42                this->root = nullptr;
 43                return;
 44            }
 45            vector<NodePtr> pool(n);
 46            for (int i = 0; i < n; ++i) {
 47                pool[i] = new Node(a[i]);
 48            }
 49            for (int i = 1; i < n+1; ++i) {
 50                if (2*i-1 < n) {
 51                    pool[i-1]->left = pool[2*i-1];
 52                }
 53                if (2*i   < n) {
 54                    pool[i-1]->right = pool[2*i];
 55                } else {
 56                    break;
 57                }
 58            }
 59            this->root = pool[0];
 60        }
 61
 62        PersistentArray<T> _new(NodePtr root) const {
 63            PersistentArray<T> res;
 64            res.root = root;
 65            res.n = this->n;
 66            return res;
 67        }
 68
 69      public:
 70        PersistentArray() : root(nullptr), n(0) {}
 71
 72        //! 配列 `a` をもとに構築する / `O(n)`
 73        PersistentArray(const vector<T> a) {
 74            _build(a);
 75        }
 76
 77        //! 位置 `k` を `v` に変更した永続配列を返す / `O(logn)` time, `O(logn)` space
 78        PersistentArray<T> set(int k, T v) const{
 79            assert(0 <= k && k < this->n);
 80            assert(this->root);
 81            NodePtr node = this->root;
 82            NodePtr new_node = node->copy();
 83            PersistentArray<T> res = _new(new_node);
 84            k++;
 85            int b = bit_length(k);
 86            for (int i = b-2; i >= 0; --i) {
 87                if ((k >> i) & 1) {
 88                    node = node->right;
 89                    new_node->right = node->copy();
 90                    new_node = new_node->right;
 91                } else {
 92                    node = node->left;
 93                    new_node->left = node->copy();
 94                    new_node = new_node->left;
 95                }
 96            }
 97            new_node->key = v;
 98            return res;
 99        }
100
101        //! 位置 `k` の値を返す / `O(logn)` time, `O(1)` space
102        T get(int k) const {
103            assert(0 <= k && k < this->n);
104            assert(this->root);
105            NodePtr node = this->root;
106            k++;
107            int b = bit_length(k);
108            for (int i = b-2; i >= 0; --i) {
109                if ((k >> i) & 1) {
110                    node = node->right;
111                } else {
112                    node = node->left;
113                }
114            }
115            return node->key;
116        }
117
118        //! 永続配列全体をコピーして返す / `O(1)` time, `O(1)` space
119        PersistentArray<T> copy() const {
120            return _new(this->root ? this->root->copy() : nullptr);
121        }
122
123        //! `vector` にして返す / `O(n)`
124        vector<T> tovector() const {
125            vector<T> a(this->n);
126            vector<NodePtr> q = {this->root};
127            for (int i = 0; i < (int)q.size(); ++i) {
128                NodePtr node = q[i];
129                a[i] = node->key;
130                if (node->left) q.emplace_back(node->left);
131                if (node->right) q.emplace_back(node->right);
132            }
133            return a;
134        }
135
136        //! 要素数を返す / `O(1)`
137        int len() const {
138            return this->n;
139        }
140
141        void print() const {
142            vector<T> a = tovector();
143            cout << "[";
144            for (int i = 0; i < (int)a.size(); ++i) {
145                cout << a[i];
146                if (i != (int)a.size()-1) {
147                    cout << ", ";
148                }
149            }
150            cout << "]" << endl;
151        }
152    };
153}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/persistent_array.cpp