Binary Lifting(ダブリング)
(misc/doubling.hpp)

• View this file on GitHub
• Last update: 2024-09-14 20:40:02+09:00
• Include: #include "misc/doubling.hpp"

Binary Lifting(ダブリング)

辺の重みがモノイドであり、各頂点の出次数が高々1のグラフが存在したとき、$i$を始点として$t$回グラフを移動したときの終点$j$とパス$(i,j)$の重みの和を前計算$\mathrm{O}(N \log \max(t))$、クエリ$\mathrm{O}(\log t)$計算するライブラリ。

TODO: 書く　わかりやすい解説

使い方

• template<typename T> BinaryLifting(k, lim, I)　$\cdots$　コンストラクタ。
  • Tはoperator +が定義されているモノイド
  • kはグラフの頂点数
  • limは移動回数の最大値
  • Iはモノイドの単位元
• set_next(k, nxt, t)　$\cdots$　$k$から$nxt$に重み$t$の辺を貼る。
• build() $\cdots$ データ構造を構築する。
• query(i, t) $\cdots$ $i$を始点として$t$回移動したときの(遷移先,始点と終点の間のパスの重みの和)を返す。遷移先が存在しない場合は($-1$, 最後に到達した点までのパスの重みの和)を返す。

Verified with

• verify/verify-yosupo-graph/yosupo-lowest-common-ancestor-doubling.test.cpp

Code

#pragma once

template <typename T>
struct BinaryLifting {
  using Data = pair<int, T>;

  const int N, LOG;
  vector<vector<Data>> table;
  T I;

  BinaryLifting(int n, uint64_t lim, const T I_ = T())
      : N(n), LOG(__lg(max<uint64_t>(lim, 1)) + 2), I(I_) {
    table.resize(LOG, vector<Data>(n, Data(-1, I)));
  }

  void set_next(int k, int nxt, const T& t) { table[0][k] = Data(nxt, t); }

  void build() {
    for (int k = 0; k + 1 < LOG; ++k)
      for (int i = 0; i < N; ++i) {
        int pre = table[k][i].first;
        if (pre == -1) {
          table[k + 1][i] = table[k][i];
        } else {
          table[k + 1][i].first = table[k][pre].first;
          table[k + 1][i].second = table[k][i].second + table[k][pre].second;
        }
      }
  }

  // i から t 回進んだ先, (地点, モノイド和) を返す
  Data query(int i, uint64_t t) const {
    T d = I;
    for (int k = LOG - 1; k >= 0; k--) {
      if ((t >> k) & 1) {
        d = d + table[k][i].second;
        i = table[k][i].first;
      }
      if (i == -1) break;
    }
    return Data(i, d);
  }

  // query(i, pow(2, k))
  inline Data query_pow(int i, int k) const { return table[k][i]; }

  // assuming graph is DAG ( edge(u, v) <-> u < v )
  // find max j | j <= t, path from i to j exists
  inline pair<uint64_t, Data> binary_search(int i, int t) {
    int thres = i;
    T d = I;
    uint64_t times = 0;
    for (int k = LOG - 1; k >= 0; k--) {
      int nxt = table[k][thres].first;
      if (nxt != -1 && nxt <= t) {
        d = d + table[k][thres].second;
        thres = nxt;
        times += 1LL << k;
      }
    }
    return make_pair(times, Data(thres, d));
  }

  // assuming graph is DAG ( edge(u, v) <-> u < v )
  // find min j | j >= t, path from i to j exists
  inline pair<uint64_t, Data> binary_search2(int i, int t) {
    int thres = i;
    T d = I;
    uint64_t times = 0;
    for (int k = LOG - 1; k >= 0; k--) {
      int nxt = table[k][thres].first;
      if (nxt != -1 && nxt >= t) {
        d = d + table[k][thres].second;
        thres = nxt;
        times += 1LL << k;
      }
    }
    return make_pair(times, Data(thres, d));
  }
};

template <typename T>
using Doubling = BinaryLifting<T>;

/**
 * @brief Binary Lifting(ダブリング)
 * @docs docs/misc/doubling.md
 */

#line 2 "misc/doubling.hpp"

template <typename T>
struct BinaryLifting {
  using Data = pair<int, T>;

  const int N, LOG;
  vector<vector<Data>> table;
  T I;

  BinaryLifting(int n, uint64_t lim, const T I_ = T())
      : N(n), LOG(__lg(max<uint64_t>(lim, 1)) + 2), I(I_) {
    table.resize(LOG, vector<Data>(n, Data(-1, I)));
  }

  void set_next(int k, int nxt, const T& t) { table[0][k] = Data(nxt, t); }

  void build() {
    for (int k = 0; k + 1 < LOG; ++k)
      for (int i = 0; i < N; ++i) {
        int pre = table[k][i].first;
        if (pre == -1) {
          table[k + 1][i] = table[k][i];
        } else {
          table[k + 1][i].first = table[k][pre].first;
          table[k + 1][i].second = table[k][i].second + table[k][pre].second;
        }
      }
  }

  // i から t 回進んだ先, (地点, モノイド和) を返す
  Data query(int i, uint64_t t) const {
    T d = I;
    for (int k = LOG - 1; k >= 0; k--) {
      if ((t >> k) & 1) {
        d = d + table[k][i].second;
        i = table[k][i].first;
      }
      if (i == -1) break;
    }
    return Data(i, d);
  }

  // query(i, pow(2, k))
  inline Data query_pow(int i, int k) const { return table[k][i]; }

  // assuming graph is DAG ( edge(u, v) <-> u < v )
  // find max j | j <= t, path from i to j exists
  inline pair<uint64_t, Data> binary_search(int i, int t) {
    int thres = i;
    T d = I;
    uint64_t times = 0;
    for (int k = LOG - 1; k >= 0; k--) {
      int nxt = table[k][thres].first;
      if (nxt != -1 && nxt <= t) {
        d = d + table[k][thres].second;
        thres = nxt;
        times += 1LL << k;
      }
    }
    return make_pair(times, Data(thres, d));
  }

  // assuming graph is DAG ( edge(u, v) <-> u < v )
  // find min j | j >= t, path from i to j exists
  inline pair<uint64_t, Data> binary_search2(int i, int t) {
    int thres = i;
    T d = I;
    uint64_t times = 0;
    for (int k = LOG - 1; k >= 0; k--) {
      int nxt = table[k][thres].first;
      if (nxt != -1 && nxt >= t) {
        d = d + table[k][thres].second;
        thres = nxt;
        times += 1LL << k;
      }
    }
    return make_pair(times, Data(thres, d));
  }
};

template <typename T>
using Doubling = BinaryLifting<T>;

/**
 * @brief Binary Lifting(ダブリング)
 * @docs docs/misc/doubling.md
 */

Back to top page