dynamic segment tree init

ソースコード

  1#include <iostream>
  2#include <cassert>
  3using namespace std;
  4
  5// DynamicSegmentTreeInit
  6namespace titan23 {
  7
  8    template <class IndexType,
  9            class T,
 10            T (*op)(T, T),
 11            T (*e)(),
 12            T (*pow)(T, IndexType)>
 13    class DynamicSegmentTreeInit {
 14      private:
 15        static int bit_length(IndexType x) {
 16            return x == 0 ? 0 : 64 - __builtin_clzll(x);
 17        }
 18
 19        struct Node;
 20        using NodePtr = Node*;
 21        NodePtr root;
 22        IndexType u;
 23        T init_val;
 24
 25        struct Node {
 26            DynamicSegmentTreeInit* dseg;
 27            NodePtr left, right;
 28            IndexType l, r;
 29            T data;
 30
 31            Node() {}
 32            Node(DynamicSegmentTreeInit* dseg, IndexType l, IndexType r) :
 33                    dseg(dseg),
 34                    left(nullptr), right(nullptr),
 35                    l(l), r(r),
 36                    data(pow(dseg->init_val, r - l)) {
 37                assert(l < r);
 38            }
 39
 40            bool is_leaf() const {
 41                return this->r - this->l == 1;
 42            }
 43
 44            void update() {
 45                this->data = e();
 46                if (this->left) {
 47                    this->data = op(this->data, this->left->data);
 48                } else {
 49                    this->data = op(this->data, pow(dseg->init_val, mid()));
 50                }
 51                if (this->right) {
 52                    this->data = op(this->data, this->right->data);
 53                } else {
 54                    this->data = op(this->data, pow(dseg->init_val, mid()));
 55                }
 56            }
 57
 58            IndexType mid() const {
 59                return (l + r) / 2;
 60            }
 61        };
 62
 63      private:
 64        T inner_prod(NodePtr node, IndexType l, IndexType r) const {
 65            if (l >= r) {
 66                return e();
 67            }
 68            if (!node) {
 69                return pow(this->init_val, r - l);
 70            }
 71            if (r <= node->l || node->r <= l) return e();
 72            if (l <= node->l && node->r <= r) return node->data;
 73            return op(
 74                inner_prod(node->left, l, min(r, node->mid())),
 75                inner_prod(node->right, max(l, node->mid()), r)
 76            );
 77        }
 78
 79        void inner_set(NodePtr node, IndexType k, T val) {
 80            if (node->is_leaf()) {
 81                node->data = val;
 82                return;
 83            }
 84            if (k < node->mid()) {
 85                if (!node->left) node->left = new Node(this, node->l, node->mid());
 86                inner_set(node->left, k, val);
 87            } else {
 88                if (!node->right) node->right = new Node(this, node->mid(), node->r);
 89                inner_set(node->right, k, val);
 90            }
 91            node->update();
 92        }
 93
 94      public:
 95
 96        DynamicSegmentTreeInit() : root(nullptr), u(0) {}
 97
 98        DynamicSegmentTreeInit(const IndexType u_, T init) {
 99            assert(u_ > 0);
100            this->u = 1ll << bit_length(u_);
101            this->root = new Node(this, 0, this->u);
102            this->init_val = init;
103        }
104
105        T prod(IndexType l, IndexType r) const {
106            return inner_prod(root, l, r);
107        }
108
109        T get(IndexType k) const {
110            NodePtr node = root;
111            while (true) {
112                if (node->is_leaf()) {
113                    return node->data;
114                }
115                if (k < node->mid()) {
116                    if (!node->left) return this->init_val;
117                    node = node->left;
118                } else {
119                    if (!node->right) return this->init_val;
120                    node = node->right;
121                }
122            }
123        }
124
125        void set(IndexType k, T val) {
126            inner_set(root, k, val);
127        }
128
129        void print() {
130            for (int i = 0; i < u; ++i) {
131                cout << get(i) << ", ";
132            }
133            cout << endl;
134        }
135    };
136}  // namespace titan23

仕様

Warning

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