セグメント木 (Segment Tree)
(DataStructure/SegmentTree/SegmentTree.py)

• View this file on GitHub
• Last update: 2021-01-02 16:36:13+09:00

概要

列に対する一点更新、区間畳み込みを $O(\log n)$ で行えるデータ構造。畳み込みはモノイドを要請する。

使い方

SegmentTree(n: int, op: Callable[[T, T], T], e: T)
長さ $n$ の Segment Tree を構築する。畳み込み演算は二項演算 op、単位元 e によって定義される。計算量 $O(n)$

• build(array: List[T]) -> None
  Segment Tree を array で初期化する。計算量 $O(n)$

• __getitem__(i: int) -> T
  $i$ 番目の要素を返す。計算量 $O(1)$

• __setitem__(i: int, val: T) -> None
  $i$ 番目の要素を val に更新する。計算量 $O(\log n)$

• all_fold() -> T
  $[0, n)$ 番目の要素の畳み込み結果を返す。計算量 $O(1)$

• fold(l: int, r: int) -> T
  $[l, r)$ 番目の要素の畳み込み結果を返す。計算量 $O(\log n)$

Verified with

• TestCase/AOJ/DSL_2_A.test.py
• TestCase/AOJ/DSL_2_B.SegTree.test.py

Code

class SegmentTree:
    def __init__(self, n, op, e):
        self.n = n
        self.op = op
        self.e = e
        self.size = 2 ** ((n - 1).bit_length())
        self.node = [self.e] * (2 * self.size)

    def __getitem__(self, i):
        return self.node[i + self.size]

    def __setitem__(self, i, val):
        i += self.size
        self.node[i] = val
        while i > 1:
            i >>= 1
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def build(self, array):
        for i, val in enumerate(array, self.size):
            self.node[i] = val
        for i in range(self.size - 1, 0, -1):
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def all_fold(self):
        return self.node[1]

    def fold(self, l, r):
        l, r = l + self.size, r + self.size
        vl, vr = self.e, self.e
        while l < r:
            if l & 1:
                vl = self.op(vl, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.op(self.node[r], vr)
            l, r = l >> 1, r >> 1
        return self.op(vl, vr)

    def max_right(self, l, f):
        if l == self.n:
            return self.n
        l += self.size
        v = self.e
        init = True
        while init or (l & -l) != l:
            init = False
            while l % 2 == 0:
                l >>= 1
            if not f(self.op(v, self.node[l])):
                while l < self.size:
                    l <<= 1
                    if f(self.op(v, self.node[l])):
                        v = self.op(v, self.node[l])
                        l += 1
                return l - self.size
            v = self.op(v, self.node[l])
            l += 1
        return self.n

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