オイラーツアー (パスに対するクエリ)
(Graph/Tree/EulerTourPathQuery.py)

• View this file on GitHub
• Last update: 2024-06-29 00:33:20+09:00

概要

オイラーツアーを行い、パスに対する一点加算、区間和取得を行うアルゴリズム。

使い方

EulerTourPathQuery(tree: Sequence[Iterable[int]])
隣接リストで表現される木 tree に対してオイラーツアーを行う。同時に一点加算、区間和取得用の Binary Indexed Tree を初期構築する。計算量 $O(V\log V)$

• lca(u: int, v: int) -> int
  頂点 u と頂点 v の最小共通祖先を返す。計算量 $O(1)$

• distance(u: int, v: int) -> int
  パス u - v の距離を返す。計算量 $O(1)$

• build(vals: Sequence[int]) -> None
  頂点 v に対する値 vals[v] を格納した配列について Binary Indexed Tree を初期構築する。

• add(u: int, val: int) -> int
  頂点 u に値 val を加算する。計算量 $O(\log V)$

• vertex_path_sum(u: int, v: int) -> int
  パス u - v 上の頂点の値の総和を返す。計算量 $O(V\log V)$

• edge_path_sum(u: int, v: int) -> int
  パス u - v 上の辺の値の総和を返す。計算量 $O(V\log V)$`

Depends on

• 一点加算・区間和取得 (DataStructure/BinaryIndexedTree/PointAddRangeSum.py)
• オイラーツアー (Graph/Tree/EulerTour.py)

Verified with

• TestCase/LibraryChecker/vertex_add_path_sum.EulerTourPathQuery.test.py

Code

from DataStructure.BinaryIndexedTree.PointAddRangeSum import BinaryIndexedTree
from Graph.Tree.EulerTour import EulerTour


class EulerTourPathQuery(EulerTour):
    def __init__(self, tree):
        super().__init__(tree, root=0)
        self.n = len(tree)
        self.bit = BinaryIndexedTree(2 * self.n)

    def build(self, vals):
        array = [0] * (2 * self.n)
        for i, idx in enumerate(self.begin):
            array[idx] = vals[i]
        for i, idx in enumerate(self.end):
            array[idx] = -vals[i]
        self.bit.build(array)

    def add(self, v, val):
        self.bit.add(self.begin[v], val)
        self.bit.add(self.end[v], -val)

    def vertex_path_sum(self, u, v):
        lca_uv = self.lca(u, v)
        res = self.bit.sum(self.begin[lca_uv], self.begin[u] + 1) \
            + self.bit.sum(self.begin[lca_uv] + 1, self.begin[v] + 1)
        return res

    def edge_path_sum(self, u, v):
        lca_uv = self.lca(u, v)
        res = self.bit.sum(self.begin[lca_uv] + 1, self.begin[u] + 1) \
            + self.bit.sum(self.begin[lca_uv] + 1, self.begin[v] + 1)
        return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page