左右からの累積和
(DataStructure/AccumulateSum/AccumulateSumLR.py)

• View this file on GitHub
• Last update: 2021-01-04 02:54:49+09:00

概要

計算量 $O(n)$ の前計算により、列に対する区間取得を計算量 $O(1)$ で行えるデータ構造。

通常の累積和の場合には、演算に関する逆元が必要であるが、この累積和には逆元が不要（二項演算と単位元をもつモノイドで十分）である。その代わりに、左端からの累積もしくは右端からの累積しか取ることができない。ABC125-C GCD on Blackboard のような問題で役立つ。

使い方

AccumulateSumLR(array: Sequence[T], op: Callable[[T, T], T], e: T)
長さ $n$ の配列 array に対して、左からの累積と右からの累積を構築する。累積は二項演算 op、単位元 e によって演算される。計算量 $O(n)$

• left_fold(upper: int) -> T
[0, upper) 番目の要素の累積を返す。計算量 $O(1)$

• right_fold(lower: int) -> T
[lower, n) 番目の要素の累積を返す。計算量 $O(1)$

Verified with

• TestCase/unittest/AccumulateSumLR.unittest.test.py

Code

class AccumulateSumLR:
    def __init__(self, array, op, e):
        self.op = op
        self.e = e
        n = len(array)
        self.left = [self.e] * (n + 1)
        self.right = [self.e] * (n + 1)
        for i in range(n):
            self.left[i + 1] = self.op(self.left[i], array[i])
        for i in reversed(range(n)):
            self.right[i] = self.op(self.right[i + 1], array[i])

    def left_fold(self, upper):
        """fold of [0, upper)"""
        return self.left[upper]

    def right_fold(self, lower):
        """fold of [lower, n)"""
        return self.right[lower]

    def fold(self, ex_idx):
        """fold all of the elements except for array[ex_idx]"""
        return self.op(self.left[ex_idx], self.right[ex_idx + 1])

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