dual_commutative_segment_tree

ソースコード

from titan_pylib.data_structures.segment_tree.dual_commutative_segment_tree import DualCommutativeSegmentTree

view on github

展開済みコード

  1# from titan_pylib.data_structures.segment_tree.dual_commutative_segment_tree import DualCommutativeSegmentTree
  2from typing import Union, Callable, TypeVar, Generic, Iterable
  3
  4T = TypeVar("T")
  5F = TypeVar("F")
  6
  7
  8class DualCommutativeSegmentTree(Generic[T, F]):
  9    """作用が可換な双対セグ木です。"""
 10
 11    def __init__(
 12        self,
 13        n_or_a: Union[int, Iterable[T]],
 14        mapping: Callable[[F, T], T],
 15        composition: Callable[[F, F], F],
 16        e: T,
 17        id: F,
 18    ) -> None:
 19        self.mapping: Callable[[F, T], T] = mapping
 20        self.composition: Callable[[F, F], F] = composition
 21        self.e: T = e
 22        self.id: F = id
 23        self.data: list[T] = [e] * n_or_a if isinstance(n_or_a, int) else list(n_or_a)
 24        self.n: int = len(self.data)
 25        self.log: int = (self.n - 1).bit_length()
 26        self.size: int = 1 << self.log
 27        self.lazy: list[F] = [id] * self.size
 28
 29    def _all_apply(self, k: int, f: F) -> None:
 30        if k < self.size:
 31            self.lazy[k] = self.composition(f, self.lazy[k])
 32            return
 33        k -= self.size
 34        if k < self.n:
 35            self.data[k] = self.mapping(f, self.data[k])
 36
 37    def _propagate(self, k: int) -> None:
 38        self._all_apply(k << 1, self.lazy[k])
 39        self._all_apply(k << 1 | 1, self.lazy[k])
 40        self.lazy[k] = self.id
 41
 42    def apply_point(self, k: int, f: F) -> None:
 43        """``k`` 番目の値に ``f`` を作用させます。
 44        :math:`O(1)` です。
 45
 46        Args:
 47            k (int): _description_
 48            f (F): _description_
 49        """
 50        assert (
 51            0 <= k < self.n
 52        ), f"IndexError: {self.__class__.__name__}.apply_point({k}, {f}), n={self.n}"
 53        self.data[k] = self.mapping(f, self.data[k])
 54
 55    def apply(self, l: int, r: int, f: F) -> None:
 56        """区間 ``[l, r)`` に ``f`` を作用させます。
 57        :math:`O(\\log{n})` です。
 58
 59        Args:
 60            l (int): _description_
 61            r (int): _description_
 62            f (F): _description_
 63        """
 64        assert (
 65            0 <= l <= r <= self.n
 66        ), f"IndexError: {self.__class__.__name__}.apply({l}, {r}, {f}), n={self.n}"
 67        if l == r:
 68            return
 69        if f == self.id:
 70            return
 71        l += self.size
 72        r += self.size
 73        data, lazy = self.data, self.lazy
 74        if (l - self.size) & 1:
 75            data[l - self.size] = self.mapping(f, data[l - self.size])
 76            l += 1
 77        if (r - self.size) & 1:
 78            data[(r - self.size) ^ 1] = self.mapping(f, data[(r - self.size) ^ 1])
 79            r ^= 1
 80        l >>= 1
 81        r >>= 1
 82        while l < r:
 83            if l & 1:
 84                lazy[l] = self.composition(f, lazy[l])
 85                l += 1
 86            if r & 1:
 87                r ^= 1
 88                lazy[r] = self.composition(f, lazy[r])
 89            l >>= 1
 90            r >>= 1
 91
 92    def all_apply(self, f: F) -> None:
 93        """区間 ``[0, n)`` に ``f`` を作用させます。
 94        :math:`O(1)` です。
 95        """
 96        self.lazy[1] = self.composition(f, self.lazy[1])
 97
 98    def all_propagate(self) -> None:
 99        for i in range(self.size):
100            self._propagate(i)
101
102    def tolist(self) -> list[T]:
103        self.all_propagate()
104        return self.data[:]
105
106    def __getitem__(self, k: int) -> T:
107        """``k`` 番目の値を取得します。
108        :math:`O(\\log{n})` です。
109        """
110        assert (
111            -self.n <= k < self.n
112        ), f"IndexError: {self.__class__.__name__}[{k}], n={self.n}"
113        if k < 0:
114            k += self.n
115        lazy = self.lazy
116        k += self.size
117        lazy_f = self.id
118        for i in range(self.log, 0, -1):
119            lazy_f = self.composition(lazy_f, lazy[k >> i])
120        return self.mapping(lazy_f, self.data[k - self.size])
121
122    def __setitem__(self, k: int, v: T) -> None:
123        assert (
124            -self.n <= k < self.n
125        ), f"IndexError: {self.__class__.__name__}[{k}] = {v}, n={self.n}"
126        if k < 0:
127            k += self.n
128        k += self.size
129        for i in range(self.log, 0, -1):
130            self._propagate(k >> i)
131        self.data[k - self.size] = v
132
133    def __str__(self):
134        return str([self[i] for i in range(self.n)])
135
136    def __repr__(self):
137        return f"{self.__class__.__name__}({self})"

仕様

class DualCommutativeSegmentTree(n_or_a: int | Iterable[T], mapping: Callable[[F, T], T], composition: Callable[[F, F], F], e: T, id: F)[source]

Bases: Generic[T, F]

作用が可換な双対セグ木です。

__getitem__(k: int) → T[source]

k 番目の値を取得します。 \(O(\log{n})\) です。

all_apply(f: F) → None[source]

区間 [0, n) に f を作用させます。 \(O(1)\) です。

all_propagate() → None[source]
apply(l: int, r: int, f: F) → None[source]

区間 [l, r) に f を作用させます。 \(O(\log{n})\) です。

Parameters:

  • l (int) – _description_

  • r (int) – _description_

  • f (F) – _description_

apply_point(k: int, f: F) → None[source]

k 番目の値に f を作用させます。 \(O(1)\) です。

Parameters:

  • k (int) – _description_

  • f (F) – _description_

tolist() → list[T][source]