hld segment tree

ソースコード

 1#include <vector>
 2#include "titan_cpplib/graph/hld.cpp"
 3#include "titan_cpplib/data_structures/segment_tree.cpp"
 4using namespace std;
 5
 6namespace titan23 {
 7
 8    /**
 9     * @brief セグ木搭載HLD / 非可換に対応
10     * 
11     * @tparam T 
12     * @tparam (*op)(T, T) 
13     * @tparam (*e)() 
14     */
15    template <class T,
16              T (*op)(T, T),
17              T (*e)()>
18    class HLDSegmentTree {
19      private:
20        titan23::HLD hld;
21        titan23::SegmentTree<T, op, e> seg, rseg;
22
23      public:
24        HLDSegmentTree(const titan23::HLD &hld) : hld(hld), seg(hld.n) {}
25
26        HLDSegmentTree(const titan23::HLD &hld, constvector<T> &a) : hld(hld) {
27            vector<T> b = hld.build_list(a);
28            this->seg = titan23::SegmentTree<T, op, e>(hld.build_list(b));
29            reverse(b.begin(), b.end());
30            this->rseg = titan23::SegmentTree<T, op, e>(hld.build_list(b));
31        }
32
33        //! `u` から `v` へのパスの総積を返す / `O(logn)`
34        T path_prod(int u, int v) const {
35            T lres = e(), rres = e();
36            while (hld.head[u] != hld.head[v]) {
37                if (hld.dep[hld.head[u]] > hld.dep[hld.head[v]]) {
38                    lres = op(lres, rseg.prod(hld.n - hld.nodein[u] - 1, hld.n - hld.nodein[hld.head[u]]));
39                    u = hld.par[hld.head[u]];
40                } else {
41                    rres = op(seg.prod(hld.nodein[hld.head[v]], hld.nodein[v] + 1), rres);
42                    v = hld.par[hld.head[v]];
43                }
44            }
45            if (hld.dep[u] > hld.dep[v]) {
46                lres = op(lres, rseg.prod(hld.n - hld.nodein[u] - 1, hld.n - hld.nodein[v]));
47            } else {
48                lres = op(lres, seg.prod(hld.nodein[u], hld.nodein[v] + 1));
49            }
50            return op(lres, rres);
51        }
52
53        //! 頂点 `k` の値を返す / `O(1)`
54        T get(const int k) const {
55            return seg.get(hld.nodein[k]);
56        }
57
58        //! 頂点 `k` の値を `v` に更新する / `O(logn)`
59        void set(const int k, const T v) {
60            seg.set(hld.nodein[k], v);
61            rseg.set(hld.n - hld.nodein[k] - 1, v);
62        }
63
64        //! 頂点 `v` の部分木の総積を返す / `O(logn)`
65        T subtree_prod(const int v) const {
66            return seg.prod(hld.nodein[v], hld.nodeout[v]);
67        }
68    };
69}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/graph/hld_segment_tree.cpp