segment tree

ソースコード

  1#include <iostream>
  2#include <vector>
  3#include <cassert>
  4using namespace std;
  5
  6namespace titan23 {
  7
  8    template <class T,
  9              T (*op)(T, T),
 10              T (*e)()>
 11    struct SegmentTree {
 12      private:
 13        int n, _size, _log;
 14        vector<T> data;
 15
 16        int bit_length(const int x) const {
 17            if (x == 0) return 0;
 18            return 32 - __builtin_clz(x);
 19        }
 20
 21      public:
 22        SegmentTree() {}
 23
 24        SegmentTree(const int n) {
 25            _build(n);
 26        }
 27
 28        SegmentTree(const vector<T> &a) {
 29            int n = (int)a.size();
 30            _build(n);
 31            for (int i = 0; i < n; ++i) {
 32                data[i+_size] = a[i];
 33            }
 34            for (int i = _size-1; i > 0; --i) {
 35                data[i] = op(data[i<<1], data[i<<1|1]);
 36            }
 37        }
 38
 39        void _build(const int n) {
 40            this->n = n;
 41            this->_log = bit_length(n);
 42            this->_size = 1 << _log;
 43            this->data.resize(this->_size*2, e());
 44        }
 45
 46        T get(int const k) const {
 47            assert(0 <= k && k < n);
 48            return data[(k<0 ? (k+n+_size) : (k+_size))];
 49        }
 50
 51        void set(int k, const T v) {
 52            assert(0 <= k && k < n);
 53            k += _size;
 54            data[k] = v;
 55            for (int i = 0; i < _log; ++i) {
 56                k >>= 1;
 57                data[k] = op(data[k<<1], data[k<<1|1]);
 58            }
 59        }
 60
 61        T prod(int l, int r) const {
 62            assert(0 <= l && l <= r && r <= n);
 63            l += _size;
 64            r += _size;
 65            T lres = e(), rres = e();
 66            while (l < r) {
 67                if (l & 1) lres = op(lres, data[l++]);
 68                if (r & 1) rres = op(data[r^1], rres);
 69                l >>= 1;
 70                r >>= 1;
 71            }
 72            return op(lres, rres);
 73        }
 74
 75        T all_prod() const {
 76            return data[1];
 77        }
 78
 79        template<typename F>  // F: function<bool (T)> f
 80        int max_right(int l, F &&f) const {
 81            assert(0 <= l && l <= _size);
 82            // assert(f(e()));
 83            if (l == n) return n;
 84            l += _size;
 85            T s = e();
 86            while (1) {
 87                while ((l & 1) == 0) {
 88                l >>= 1;
 89                }
 90                if (!f(op(s, data[l]))) {
 91                while (l < _size) {
 92                    l <<= 1;
 93                    if (f(op(s, data[l]))) {
 94                    s = op(s, data[l]);
 95                    l |= 1;
 96                    }
 97                }
 98                return l - _size;
 99                }
100                s = op(s, data[l]);
101                ++l;
102                if ((l & (-l)) == l) break;
103            }
104            return n;
105        }
106
107        template<typename F>  // F: function<bool (T)> f
108        int min_left(int r, F &&f) const {
109            assert(0 <= r && r <= n);
110            // assert(f(e()));
111            if (r == 0) return 0;
112            r += _size;
113            T s = e();
114            while (r > 0) {
115                --r;
116                while (r > 1 && (r & 1)) {
117                r >>= 1;
118                }
119                if (!f(op(data[r], s))) {
120                while (r < _size) {
121                    r = (r << 1) | 1;
122                    if (f(op(data[r], s))) {
123                    s = op(data[r], s);
124                    r ^= 1;
125                    }
126                }
127                return r + 1 - _size;
128                }
129                s = op(data[r], s);
130                if ((r & (-r)) == r) break;
131            }
132            return 0;
133        }
134
135        vector<T> tovector() const {
136            vector<T> res(n);
137            for (int i = 0; i < n; ++i) {
138                res[i] = get(i);
139            }
140            return res;
141        }
142
143        void print() const {
144            cout << '[';
145            for (int i = 0; i < n-1; ++i) {
146                cout << get(i) << ", ";
147            }
148            if (n > 0) cout << get(n-1);
149            cout << ']' << endl;
150        }
151    };
152}  // namespace titan23

仕様

Warning

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