SegmentTree
(lib/data_structure/segment_tree.py)

• View this file on GitHub
• Last update: 2022-08-20 14:37:04+09:00

SegmentTree

モノイド $T$ の要素数 $N$ の配列に対して、要素の一点変更と任意区間のモノイド積の取得をともに $O(\log N)$ で行うことができるデータ構造。

Implementations

def __init__(self, n: int, op: Callable[[T, T], T], e: T)

サイズ n の SegmentTree を単位元で初期化する
op : モノイド積を計算する関数
e : モノイドの単位元
$O(N)$

---

def build(self, a: Sequence[T])

a で初期化する
a のサイズが SgementTree のサイズより大きい場合は IndexError を送出する
$O(N)$

---

def set(self, i: int, x: T)

i 番目の要素を x に更新する
i が SegmentTree のサイズより大きい場合は IndexError を送出する
$O(\log{N})$

---

def query(self, l: int, r: int) -> T

区間 [l, r) の和を返す
l >= r のときは単位元を返す
l または r が SegmentTree のサイズより大きい場合は IndexError を送出する
$O(\log{N})$

---

def at(self, i: int) -> T

i 番目の要素の値を返す
i が SegmentTree のサイズより大きい場合は IndexError を送出する
$O(\log{N})$

---

Verified with

• verify/data_structure/point_add_range_sum__segment_tree.test.py
• verify/data_structure/point_set_range_composite.test.py
• verify/data_structure/static_range_sum__segment_tree.test.py
• verify/data_structure/staticrmq.test.py

Code

T = "Monoid"


class SegmentTree:
    def __init__(self, n: int, op, e):
        self._n = n
        self._op = op
        self._e = e
        self._a = [self._e] * (n * 2)

    def build(self, a):
        for i, ai in enumerate(a, self._n):
            self._a[i] = ai
        for i in range(self._n - 1, 0, -1):
            self._a[i] = self._op(self._a[2 * i], self._a[2 * i + 1])

    def set(self, i: int, x: T):
        i += self._n
        self._a[i] = x
        while i > 1:
            i //= 2
            self._a[i] = self._op(self._a[2 * i], self._a[2 * i + 1])

    def query(self, l: int, r: int) -> T:
        l += self._n
        r += self._n
        vl, vr = self._e, self._e
        while l < r:
            if l % 2:
                vl = self._op(vl, self._a[l])
                l += 1
            if r % 2:
                vr = self._op(self._a[r - 1], vr)
            l //= 2
            r //= 2
        return self._op(vl, vr)

    def at(self, i: int) -> T:
        return self._a[i + self._n]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.6/x64/lib/python3.10/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.10.6/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page