/
xor_disjoint_sparse_table.hpp
55 lines (52 loc) · 1.39 KB
/
xor_disjoint_sparse_table.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
template <typename Monoid>
struct Xor_Disjoint_Sparse_Table {
using MX = Monoid;
using X = typename Monoid::value_type;
int log;
vvc<X> dat;
Xor_Disjoint_Sparse_Table() {}
Xor_Disjoint_Sparse_Table(int n) { build(n); }
template <typename F>
Xor_Disjoint_Sparse_Table(int n, F f) {
build(n, f);
}
Xor_Disjoint_Sparse_Table(const vc<X>& v) { build(v); }
void build(int m) {
build(m, [](int i) -> X { return MX::unit(); });
}
void build(const vc<X>& v) {
build(len(v), [&](int i) -> X { return v[i]; });
}
template <typename F>
void build(int m, F f) {
log = 0;
while ((1 << log) < m) ++log;
assert(m == (1 << log));
// 各 k, i に対して、prod_{0<=j<2^k} A[i^j] を持つ
dat.resize(log + 1);
dat[0].reserve(1 << log);
FOR(i, 1 << log) dat[0].eb(f(i));
FOR(k, log) {
dat[k + 1].assign(1 << log, MX::unit());
FOR(i, 1 << log) {
dat[k + 1][i] = MX::op(dat[k][i], dat[k][i ^ (1 << k)]);
}
}
}
// calculate prod_{l<=i<r} A[x xor i], in O(log N) time.
X prod(int l, int r, int xor_val) {
X xl = MX::unit(), xr = MX::unit();
FOR(k, log + 1) {
if (l >= r) break;
if (l & 1 << k) {
xl = MX::op(xl, dat[k][l ^ xor_val]);
l += (1 << k);
}
if (r & 1 << k) {
r -= (1 << k);
xr = MX::op(dat[k][r ^ xor_val], xr);
}
}
return MX::op(xl, xr);
}
};