## 概要
木を大きいパスから順に分割して列に変換することで、木に対して区間クエリが使えるデータ構造。  
区間クエリ部分を SegmentTree で実装している為、モノイドであれば何でも、木に対して区間演算が O(logN) で適用可能。  
(勿論更新も1回当たり O(logN) で可能。)

## 作成part
以下二つの記事を参考に実装。
頂点も辺も載せることが出来る。頂点は簡単だが、辺は深さが深い方のノードに重みを載せることでうまく管理出来る。  

[参考記事1](https://qiita.com/Pro_ktmr/items/4e1e051ea0561772afa3#2-hl-%E5%88%86%E8%A7%A3%E3%81%AE%E5%AE%9F%E8%A3%85%E6%96%B9%E9%87%9D)

[参考記事2](https://qiita.com/ageprocpp/items/8dfe768218da83314989)

## method
- addEdge(u, v) : 木構造の辺追加
- set(u,x) : 各頂点に乗せる値
- set(u,v,x) : 各辺に乗せる値（関数をオーバーロードして引数の数で使い分け）
- build() : 辺を N-1 本追加した後に発火することで重軽分解を行う
- query(u, v) : 木上の u → v のパスにおいて、Segment Tree にて設定した演算を O(logN) で行う

## Program
```cpp
// ↓~~~~~~~~~~ Heavy-Light-Deconposition ~~~~~~~~~~↓ //
// モノイド設定
using S = long long;
S Sum_e(){return 0;}
S Sum_op(S a,S b){return a+b;}

class HLD{
    public:
        HLD() : n(0){}
        explicit HLD(const int _n, bool _ef){
            n = _n;
            ef = _ef; // 辺更新ならtrue , 頂点更新ならfalse
            part_size.assign(n,1);
            shallow.assign(n,0);
            parent.assign(n,0);
            Graph.assign(n,{});
            depth.assign(n,0);
            hld.assign(n,0);
            sg = segtree<S,Sum_op,Sum_e>(n);
        }

        inline void addEdge(int u, int v){
            Graph[u].emplace_back(v);
            Graph[v].emplace_back(u);
        }

        void build(){
            dfs(0,-1);            // parent & depth 算出
            HLDecomposition(0,0); // HL分解
        }

        long long query(int u, int v){
            long long res = 0;
            while(shallow[u] != shallow[v]){
                if(depth[shallow[u]] > depth[shallow[v]])swap(u,v);
                // 深いHLD要素を遡る
                res += sg.prod(hld[shallow[v]], hld[v]+1);
                v = parent[shallow[v]];
            }
            if(depth[u] > depth[v])swap(u,v);
            res += sg.prod(hld[u]+ef, hld[v]+1);
            return res;
        }

        inline void set(int idx, long long x){
            // 頂点set
            sg.set(hld[idx],x);
        }
        inline void set(int u, int v, long long x){
            // 辺set
            if(depth[u] > depth[v])swap(u,v);
            sg.set(hld[v],x);
        }

    private:
        bool ef;
        int n, child;
        // hld     : 元の頂点 → HLD要素
        // r_hld   : HLD要素 → 元の頂点
        // shallow : HLD要素の最も浅い頂点
        vector<int> part_size, r_hld, shallow, hld, depth, parent;
        vector<vector<int>> Graph;
        segtree<S,Sum_op,Sum_e> sg;

        inline void HLDecomposition(int v, const int a){
            hld[v] = r_hld.size();
            r_hld.emplace_back(v);
            shallow[v] = a;

            if( (Graph[v].size() == 1 && Graph[v][0] == parent[v]) || Graph[v].size() == 0 )return;

            int max_size = -1, max_idx = 0;
            for(int i=0;i<Graph[v].size();i++){
                child = Graph[v][i];
                if(child == parent[v])continue;
                if(max_size < part_size[child]){
                    max_size = part_size[child];
                    max_idx = i;
                }
            }
            HLDecomposition(Graph[v][max_idx],a);
            for(int i=0; i<Graph[v].size(); i++){
                child = Graph[v][i];
                if(child == parent[v])continue;
                if(i != max_idx){
                    HLDecomposition(child,child);
                }
            }
        }

        inline void dfs(const int &now, const int pre){
            if(pre == -1)depth[now] = 0;
            else depth[now] = depth[pre]+1;
            parent[now] = pre;
            for(auto to:Graph[now]){
                if(to == pre)continue;
                dfs(to,now);
                part_size[now] += part_size[to];
            }
        }
};
// ↑~~~~~~~~~~ Heavy-Light-Deconposition ~~~~~~~~~~↑ //

// ※ buildしてからじゃないと重みset出来ないので注意
```

Heavy Light Decomposition

## 概要
木を経路で見ることで LCA や ノードの最短距離 が O(logN) で求まるデータ構造。
辺の重みも1回当たり O(logN) で変更可能な為、オンラインクエリにも対応出来る。

## 作成part

[参考記事](https://qiita.com/recuraki/items/72e37eb9be9f71bc623a)

## method
- addEdge(u, v, w) : ノード u, v 間の重みが w の辺を追加する
- addVCost(i, w) : ノード i 自体に存在する頂点の重みを追加する
- changeECost(u, v, w) : ノード u, v 間の重みを w に変更する（辺を既に存在するものと仮定）
- lca(u, v) : ノード u, v の最近共通祖先（LCA）を返す

## Program
```cpp
// モノイド設定
using S = long long;
S Sum_e(){return 0;}
S Sum_op(S a,S b){return a+b;}

using U = pair<int,int>;
U Min_e(){return pair(1e9,1e9);}
U Min_op(U a,U b){return min(a,b);}

class EulerTour{
    public:
        EulerTour() : n(0),turn(0){}
        explicit EulerTour(const int &_n){
            n = _n;
            turn = 0;
            Graph.assign(n,{});
            vw.assign(n,0);
            finish.assign(n,0);
            discover.assign(n,0);
            v_cost1 = segtree<S, Sum_op, Sum_e>(2*n);
            e_cost1 = segtree<S, Sum_op, Sum_e>(2*n);
            v_cost2 = segtree<S, Sum_op, Sum_e>(2*n);
            e_cost2 = segtree<S, Sum_op, Sum_e>(2*n);
            depth_visit = segtree<U, Min_op, Min_e>(2*n);
        }

        inline void addEdge(const int &u, const int &v, const long long &w){
            Graph[u].emplace_back(pair(v,w));
            Graph[v].emplace_back(pair(u,w));
        }

        inline void addVCost(const int &i,const int &w){vw[i] = w;}

        inline void changeECost(int u, int v, const int &nw){
            // ※ Graph自体の更新はしていない
            if(discover[u] > discover[v])swap(u,v);
            // 辺は2回しか通らない → O(logN)で更新可
            e_cost1.set(discover[v],nw);
            e_cost2.set(discover[v],nw);
            e_cost2.set(finish[v],-nw);
        }

        inline S distV(const int &u, const int &v){return rootV(u) + rootV(v) - 2*rootV(lca(u,v)) + vw[lca(u,v)];}
        inline S distE(const int &u, const int &v){return rootE(u) + rootE(v) - 2*rootE(lca(u,v))               ;}
        inline S partV(const int &root){return v_cost1.prod(discover[root]  ,finish[root]);}
        inline S partE(const int &root){return e_cost1.prod(discover[root]+1,finish[root]);}

        inline int lca(int u, int v){
            if(u == v)return u;
            if(discover[u] > discover[v])swap(u,v);
            return depth_visit.prod(discover[u],finish[v]+1).second;
        }

        inline void build(){dfs(0,-1,0,0);}

    private:
        int n, turn;
        vector<vector<pair<int,long long>>> Graph;
        segtree<S, Sum_op, Sum_e> v_cost1, e_cost1, v_cost2, e_cost2;
        segtree<U, Min_op, Min_e> depth_visit;
        vector<long long> vw, discover, finish;

        // 0 → v の頂点・辺cost
        inline long long rootV(const int &v){return v_cost2.prod(0,discover[v]+1);}
        inline long long rootE(const int &v){return e_cost2.prod(1,discover[v]+1);}

        void dfs(const int &now, const int &pre,const int &w, const int &d){
            // 行きがけ処理
            discover[now] = turn;
            depth_visit.set(turn,U(d,now));
            v_cost1.set(turn,vw[now]);
            v_cost2.set(turn,vw[now]);
            e_cost1.set(turn,w);
            e_cost2.set(turn,w);
            turn++;
            for(auto &&[next,nw]:Graph[now]){
                if(next == pre)continue;
                dfs(next,now,nw,d+1);
            }
            // 帰りがけ処理
            finish[now] = turn;
            if(pre != -1)depth_visit.set(turn,U(d-1,pre));
            v_cost1.set(turn,0);
            e_cost1.set(turn,0);
            v_cost2.set(turn,-vw[now]);
            e_cost2.set(turn,-w);
            turn++;
        }
};
```

Euler Tour

## 概要
Disjoint Set Union (別名 union find) に重みの概念を取り入れたデータ構造。
通常の union find はただのグループ分けだが、重み付きの union find は連結判定だけでなく、各ノードの重みの差が適しているか否かも求めることが出来る。
雑に書くと、1 クエリ当たり O(logN) だが、AtCoder Library の DSU を参考に作成しているため経路圧縮がされていて高速で、均し計算量が O(α(n)) （α(n) : アッカーマン関数の逆関数）で抑えられる。

union find に関しては下記を参照。

[参照記事1](https://algo-method.com/descriptions/132)

union find の計算量に関しては下記を参照。

[参照記事2](https://qiita.com/kopricky/items/3e5847ab1451fe990367)

## method
- merge(a, b, w) : ノード a, b 間の重みが w であるとしてノードを結合する
- same(a, b) : ノード a, b が同じ連結成分に存在するか否かを返す
- leader(a) : ノード a が存在する連結成分の一番の親要素を返す
- size(a) : ノード a が存在する連結成分のサイズを返す
- weight(a) : ノード a の重みを返す
- diff(a, b) : ノード a, b の重みの差分を返す
- groups() : 各連結成分を 1 つの配列としてまとめた二次元配列を返す

## Program
```cpp
struct weighted_dsu {
    // ACLよりUF写経
    public:
    // expricit：コンストラクタに付与で暗黙の型変換無向化
    weighted_dsu() : _n(0) {}
    explicit weighted_dsu(int n) : _n(n), parent_or_size(n, -1), diff_weight(n,0) {}

    int merge(int a, int b, ll w) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);

        // weight[b] = weight[a] + w となるようにmerge
        // ※ 連結成分のmergeだから weightの差分が重みに反映
        w += weight(a); w -= weight(b);

        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y), w = -w;
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;

        diff_weight[y] = w;

        // 連結成分が大きい方のleaderが返り値
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    // 親ノードに行くまでがO(α(n))
    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        int r = leader(parent_or_size[a]);
        diff_weight[a] += diff_weight[parent_or_size[a]];
        return parent_or_size[a] = r;
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    int weight(ll x){
        leader(x); // 経路圧縮 ( diffを現在の状態に反映 )
        return diff_weight[x];
    }

    int diff(ll x, ll y){
        return weight(y)-weight(x);
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                          [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

    private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
    std::vector<ll> diff_weight;
};
```

Weighted Disjoint Set Union

## 概要
別名 Binary Indexed Tree ( BIT )。

## method
- ???

## Program
```cpp
struct BIT{
    public:
        BIT(ll _n){
            n = _n;
            data.resize(n);
        }
        void add(ll i,ll x){
            i++; // 1-indexed (LSBを用いる都合上)
            while(i <= n){
                data[i-1] += x;
                i += (i & -i); // LSBを足した先にも考慮
            }
        }
        ll sum(ll l,ll r){
            return _sum(r) - _sum(l); // 裏関係
        }

    private:
        ll n;
        vector<ll> data;
        ll _sum(ll i){
            ll s = 0;
            // ここのiは1-indexed
            while(i){
                s += data[i-1];
                i -= (i & -i);
            }
            return s;
        }
};
```

Fenwick Tree

## 概要
連続部分列の hash を O(1) で取得可能なデータ構造。  

## 作成part
### Hash関数
- 基数 と 法 を定めて、法の下で 基数の累乗を線形結合的にしてhashを得る。  
- N ≦ 10^5 なら、基数を 2^61 - 1 にしてる為、hash衝突がほとんど起こらない。( sqrt(基数) くらいだと 50% 位衝突 )

### 法 と 基数
- 法は **2^61 - 1** 固定。( 2進数の剰余は bit shift & フェルマーの小定理 により、剰余が高速に計算可能な為。 )
- 基数は 乱択。ただ 文字列を扱う際は **128** 以上、数列を扱う場合は最大値以上 を取る必要あり。( 線形性を利用しており、基数の累乗が他の累乗に影響を与えないようにする為 )
- また基数は **原子根** にするとより衝突が起こりにくい。

[参考資料1 (原始根の求め方) ](https://trap.jp/post/1036/)

[参考資料2 (原始根参考実装) ](https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5055704#1)

## method
- mulMod(x ,y) : 積の剰余を取得する関数。( \_\_int128\_t に対して % は遅い為作成する )
- get(l,r) : インスタンス作成時の文字列の \[l,r) の部分列の hash を求める関数。(累積和的に hash が求まる)

## Program
```cpp
using ull = unsigned long long;
vector<ull> powr; // 基数の累乗

class RollingHash {
    public:
    RollingHash(const string &s){
        if(base == 0){
            // base を 2^61-1の原始根 & 1e9以上 で初期化
            random_device rnd;
            mt19937 mt(rnd());
            uniform_int_distribution<ull> rand(1,INT_MAX);
            while(1){
                ull k = rand(mt);
                base = modPow(37,k);
                if(euclid(Mod-1,k) == 1 && base > 1e9)break;
            }
        }
        powr.assign(1,1);
        int size = s.size();
        hash.assign(size+1,0);
        // 左端~の hash 前計算
        for(int i=0; i<size; i++){
            hash[i+1] = mulMod(hash[i],base) + s[i];
            hash[i+1] = getMod(hash[i+1]);
        }
    }

    ull get(int l, int r){
        ull res = hash[r] - mulMod(hash[l],getPow(r-l));
        return getMod(res + Positivizer);
    }

    private:
    static const ull Mod = (1LL << 61) - 1;
    static const ull Positivizer = Mod * 7;
    static ull base;  // 基数
    vector<ull> hash; // hash の cash

    static ull getPow(int n){
        while(powr.size() <= n){
            // 次の基数の累乗を求める
            powr.push_back(mulMod(powr.back(), base));
        }
        return powr[n];
    }

    static ull mulMod(ull x,ull y){
        // Fermatの小定理 & 2進数のmod を利用
        __int128_t t = (__int128_t) x*y;
        t = (t >> 61) + (t & Mod);
        if(t >= Mod)t -= Mod;
        return (ull)t;
    }

    static ull getMod(ull val){
        val = (val >> 61) + (val & Mod);
        if(val >= Mod)val -= Mod;
        return (ull)val;
    }

    static ull euclid(ull a,ull b){
        if(b != 0)return euclid(b,a%b);
        else return a;
    }

    static ull modPow(ull a, ull b) {
        ll res= 1;
        for(; b; a=getMod(a*a), b>>=1) {
            if(b & 1)res = getMod(res*a);
        }
        return res;
    }
};
ull RollingHash::base;
```

Rolling Hash

## 概要
盤面(状態) をhash化出来るデータ構造。  
起源は、Zobristさんという方がチェスのコンピュータを作成する時に、チェスの盤面をhash化するために作成したhash方法とのこと。

## 作成part
### hash関数
- ある1要素に対して乱数(hash)を割り当てる。( 要素は何でもよい )
- 状態v (初期0) を定義して、そこにhash を xor させたものを、$その要素が含まれた盤面のhash$として扱う。

### 確率論
- Zobrist Hash を言い換えるならば ”確率論”。
- パッと見衝突が不安だが、自分のprogramを見ると分かるように、要素の種類が 1e6 とかなら、hash衝突の確率は宝くじ 1 等当選と同じくらい低い。  

[参考記事1](https://zenn.dev/firedial/articles/b4ec2380f41c6c)

[参考記事2](https://qiita.com/a_uchida/items/bec46c20fd2965c6e1a0)

### method
- init(): 保持してるhashを0にする。( O(1) )
- get(): 今現在の盤面のhashを返す。( O(1) )
- flip(x): xからhashを求める (過去にhashを求めた場合はそれを再利用)。そしてその分だけ hash を xor する。( O(1) )

## Program
```cpp
template <class S>
struct Zobrist_hash_set {
    public:
    Zobrist_hash_set() : v(0) {
        mt.seed(rand());
        rnd = uniform_int_distribution<ll>(-LLONG_MAX, LLONG_MAX);
   }

    // 64bit整数値でhashを取る → max(N) = 2^20 = 104856 ≒ 1e6 の時
    // hash衝突確率p :
    // 1-p <= ( (2^64-n)/2^64 )^n ≒ 0.99999994039
    // p ≒ 1e(-7) (宝くじ1等の当選確率位)

    // 盤面のhashに関しても同様
    // → 調べたい盤面が高々1e6位の時は基本衝突しない。

    // 今現在の状態をvとして、xのhashをxorしてあげる
    void flip(const S& x) {
        // x 初出現 → 新hash値を割当
        if (!x_to_hash.count(x)) {
            x_to_hash[x] = rnd(mt);
        }
    
        // 状態のhash値更新
        v ^= x_to_hash[x];
    }
    
    // hash初期化
    void init() { v = 0; }
    
    // 現時点の状態hash値を返す．
    ll get() { return v; }
    
    private:
    // hash値
    ll v;

    // 各 x ∈ X に対するハッシュの割当
    unordered_map<S, ll> x_to_hash;
    mt19937_64 mt;
    uniform_int_distribution<ll> rnd;
};
```

Zobrist Hash

## 概要
木構造における任意の2ノードの最近共通祖先を 1 クエリ当たり O(logN) で求めるためのデータ構造。
最近共通祖先については下記を参照。

[参考記事](https://algo-logic.info/lca/)

## method
- init(Graph, root : option) : 隣接リストのグラフから、最近共通祖先を求めるにあたって必要なダブリングの前計算を行う
- query(u, v) : 二つのノード u, v の最近共通祖先を O(logN) で求める

## Program
```cpp
struct Edge {
    ll to;
};
using Graph = vector<vector<Edge>>;
struct LCA {
    vector<vector<int>> parent;
    vector<int> dist;
    LCA(const Graph &G, int root = 0) { init(G, root); }
    // 初期化
    void init(const Graph &G, int root = 0) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++;
        //parent[i][j] : 2^i先の親
        parent.assign(K, vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                } else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }
    void dfs(const Graph &G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e.to != p) dfs(G, e.to, v, d + 1);
        }
    }
    int query(int u, int v) {
        if (dist[u] < dist[v]) swap(u, v);
        int K = parent.size();
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
};
```

Latest Common Ancestor

## 概要
1点更新・区間演算(※)が1回当たり O(logN) 出来るデータ構造。  

## 作成part
### モノイド
- SegTree上に乗せる演算のこと。以下の2つの規則が成り立つ演算の事を言う。  

集合 S とその上の二項演算 •: S × S → S が与えられた時、
1. 結合律：S の任意の元 a, b, c に対して、(a • b) • c = a • (b • c)
2. 単位元の存在：S の元 e が存在して、S の任意の元 a に対して e • a = a • e = a   

※単位減は演算の前後で値が変化しない元のこと。足し算における0、 掛け算における1。  

## method
- set(i, x) : i 番目のノードに x を代入する
- prod(l, r) : [l, r) の半開区間において、予め定義した operation を O(logN) で行う
- all_prod() : 全ての区間における operation の結果を O(1) で行う

## Program
```cpp
template<typename S,S(*op)(S,S),S(*e)()>
struct SegTree{
    SegTree() : n(0){}
    explicit SegTree(ll _n){
        n = _n;
        log2 = 0;
        while((1LL << log2) < n)log2++;
        size = 1LL << log2;
        data = vector<S>(2*size,e());
    }

    void set(ll i,S x){
        // dataの葉のidxを参照する為に足す
        i += size;

        // dataの中で更新を反映させるべきnodeを捜査
        // ※完全二分木を書けば分かる
        data[i] = x; // data[i]はupdate()では不可(葉を参照してるから)
        while(i > 1){
            i /= 2;
            update(i);
        }
    }

    void update(ll i){
        data[i] = op(data[2*i],data[2*i+1]);
    }

    S prod(ll l,ll r){
        l += size, r += size;
        S sml = e(),smr = e();
        while(l < r){
            // ここの処理はmemo参照
            if(l & 1)sml = op(sml,data[l++]);
            if(r & 1)smr = op(data[--r],smr);
            l /= 2, r /= 2;
        }
        return op(sml,smr);
    }

    S all_prod(){
        return data[1];
    }

    private:
        ll size;
        ll log2;
        ll n;
        vector<S> data;
};
```

Heavy Light Decomposition tree 2023-05-23 重軽分解	Euler Tour tree 2023-05-23 オイラーツアー
Weighted Disjoint Set Union dsu 2023-05-23 重み付き UnionFind	Fenwick Tree tree 2023-05-23 Binary Indexed Tree
Rolling Hash hash 2023-05-23 ローリングハッシュ	Zobrist Hash hash 2023-05-23 Zobrist Hash
Latest Common Ancestor doubling 2023-05-23 最近共通祖先	Segment Tree tree 2023-05-23 セグメントツリー