sparse table

ソースコード

 1#include <iostream>
 2#include <vector>
 3#include <cassert>
 4using namespace std;
 5
 6// SparseTable
 7namespace titan23 {
 8
 9    template <class T,
10              T (*op)(T, T),
11              T (*e)()>
12    struct SparseTable {
13      private:
14        int n;
15        vector<vector<T>> data;
16
17      public:
18        SparseTable() {}
19        SparseTable(vector<T> &a) : n((int)a.size()) {
20            int log = 32 - __builtin_clz(n) - 1;
21            data.resize(log+1);
22            data[0] = a;
23            for (int i = 0; i < log; ++i) {
24                int l = 1 << i;
25                const vector<int> &pre = data[i];
26                vector<int> &nxt = data[i+1];
27                int s = pre.size();
28                nxt.resize(s-l);
29                for (int j = 0; j < s-l; ++j) {
30                    nxt[j] = op(pre[j], pre[j+l]);
31                }
32            }
33        }
34
35        T prod(const int l, const int r) const {
36            assert(0 <= l && l <= r && r < n);
37            if (l == r) return e();
38            int u = 32 - __builtin_clz(r-l) - 1;
39            return op(data[u][l], data[u][r-(1<<u)]);
40        }
41
42        T get(const int k) const {
43            assert(0 <= k && k < n);
44            return data[0][k];
45        }
46
47        int len() const {
48            return n;
49        }
50
51        void print() const {
52            cout << '[';
53            for (int i = 0; i < n-1; ++i) {
54                cout << data[0][i] << ", ";
55            }
56            if (n > 0) {
57                cout << data[0][n-1];
58            }
59            cout << ']' << endl;
60        }
61    };
62}  // namespace titan23

仕様

Warning

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