dynamic lazy segment tree util

ソースコード

 1#include "titan_cpplib/data_structures/dynamic_lazy_segment_tree.cpp"
 2
 3namespace range_add_range_sum {
 4    using S = long long;
 5    using F = long long;
 6    using IndexType = long long;
 7    const int bit = 30;
 8    const int msk = (1ll << bit) - 1;
 9
10    S op(S a, S b) {
11        long long a0 = a >> bit, a1 = a & msk;
12        long long b0 = b >> bit, b1 = b & msk;
13        return (a0 + b0) << bit | (a1 + b1);
14    }
15
16    S e() {
17        return 0;
18    }
19
20    S mapping(F f, S s) {
21        long long s0 = s >> bit, s1 = s & msk;
22        return (s0 + f*s1) << bit | s1;
23    }
24
25    F composition(F f, F g) {
26        return f + g;
27    }
28
29    F id() {
30        return 0;
31    }
32
33    S pow(S s, IndexType k) {
34        long long s0 = s >> bit, s1 = s & msk;
35        return (s0 * k) << bit | (s1 * k);
36    }
37
38    // 初期値は1
39    titan23::DynamicLazySegmentTree<IndexType, S, op, e, F, mapping, composition, id, pow> pst(1e9, 1);
40    IndexType l, r;
41    int res = pst.prod(l, r) >> bit;
42}

仕様

Warning

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