cumulative_sum

ソースコード

from titan_pylib.data_structures.cumulative_sum.cumulative_sum import CumulativeSum

view on github

展開済みコード

 1# from titan_pylib.data_structures.cumulative_sum.cumulative_sum import CumulativeSum
 2from typing import Iterable
 3
 4
 5class CumulativeSum:
 6    """1次元累積和です。"""
 7
 8    def __init__(self, a: Iterable[int], e: int = 0):
 9        """
10        :math:`O(n)` です。
11
12        Args:
13          a (Iterable[int]): ``CumulativeSum`` を構築する配列です。
14          e (int): 単位元です。デフォルトは ``0`` です。
15        """
16        a = list(a)
17        n = len(a)
18        acc = [e] * (n + 1)
19        for i in range(n):
20            acc[i + 1] = acc[i] + a[i]
21        self.n = n
22        self.acc = acc
23        self.a = a
24
25    def pref(self, r: int) -> int:
26        """区間 ``[0, r)`` の演算結果を返します。
27        :math:`O(1)` です。
28
29        Args:
30          r (int): インデックスです。
31        """
32        assert (
33            0 <= r <= self.n
34        ), f"IndexError: {self.__class__.__name__}.pref({r}), n={self.n}"
35        return self.acc[r]
36
37    def all_sum(self) -> int:
38        """区間 `[0, n)` の演算結果を返します。
39        :math:`O(1)` です。
40
41        Args:
42          l (int): インデックスです。
43          r (int): インデックスです。
44        """
45        return self.acc[-1]
46
47    def sum(self, l: int, r: int) -> int:
48        """区間 `[l, r)` の演算結果を返します。
49        :math:`O(1)` です。
50
51        Args:
52          l (int): インデックスです。
53          r (int): インデックスです。
54        """
55        assert (
56            0 <= l <= r <= self.n
57        ), f"IndexError: {self.__class__.__name__}.sum({l}, {r}), n={self.n}"
58        return self.acc[r] - self.acc[l]
59
60    prod = sum
61    all_prod = all_sum
62
63    def __getitem__(self, k: int) -> int:
64        assert (
65            -self.n <= k < self.n
66        ), f"IndexError: {self.__class__.__name__}[{k}], n={self.n}"
67        return self.a[k]
68
69    def __len__(self) -> int:
70        return len(self.a)
71
72    def __str__(self) -> str:
73        return str(self.acc)
74
75    __repr__ = __str__

仕様

class CumulativeSum(a: Iterable[int], e: int = 0)[source]

Bases: object

1次元累積和です。

all_prod() → int

区間 [0, n) の演算結果を返します。 \(O(1)\) です。

Parameters:

  • l (int) – インデックスです。

  • r (int) – インデックスです。

all_sum() → int[source]

区間 [0, n) の演算結果を返します。 \(O(1)\) です。

Parameters:

  • l (int) – インデックスです。

  • r (int) – インデックスです。

pref(r: int) → int[source]

区間 [0, r) の演算結果を返します。 \(O(1)\) です。

Parameters:

r (int) – インデックスです。

prod(l: int, r: int) → int

区間 [l, r) の演算結果を返します。 \(O(1)\) です。

Parameters:

  • l (int) – インデックスです。

  • r (int) – インデックスです。

sum(l: int, r: int) → int[source]

区間 [l, r) の演算結果を返します。 \(O(1)\) です。

Parameters:

  • l (int) – インデックスです。

  • r (int) – インデックスです。