dynamic segment tree

ソースコード

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

仕様

Warning

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