Imos 法
(Imos.py)

View this file on GitHub
Last update: 2024-01-28 00:41:24+09:00

Outline

最初に $M$ 個の区間加算クエリが与えられた後の $Q$ 個の一点取得クエリの処理をまとめて $O(M + Q)$ 時間で行うことができる.

Theory

$R$ を環として, $\mathcal{A}$ を $R$ を要素に持つ列全体の集合とする. このとき, $\mathcal{A}$ は区間ごとの和とスカラー倍によって, $R$ 係数の加群と見ることができる.

写像 $D: \mathcal{A} \to \mathcal{A}$ を

\[D\boldsymbol{e}_n := \boldsymbol{e}_n - \boldsymbol{e}_{n+1}\]

となるような線形写像で定める. ただし, $\boldsymbol{e}_n$ とは, 第 $n$ 項のみ $1$ でそれ以外が全て $0$ である列とする.

すると,

\[D \left(\sum_{n=l}^r \boldsymbol{e}_n \right) = \sum_{n=l}^r D \boldsymbol{e}_n = \sum_{n=l}^r (\boldsymbol{e}_n - \boldsymbol{e}_{n+1}) = \boldsymbol{e}_l - \boldsymbol{e}_{r+1}\]

になる.

従って, $Q$ 個の区間加算クエリの合計を $D$ で送った像は次のように, $2N$ 個の項の和で表すことができる.

\[\begin{align*} D \left(\sum_{q=1}^Q \left( \alpha_q \sum_{n={l_q}}^{r_q} \boldsymbol{e}_n \right) \right) &= \sum_{q=1}^Q \alpha_q \left(D \sum_{n={l_q}}^{r_q} \boldsymbol{e}_n \right) \\ &= \sum_{q=1}^Q \alpha_q (\boldsymbol{e}_{l_q} - \boldsymbol{e}_{r_q + 1}) \\ &= \sum_{q=1}^Q (\alpha_q \boldsymbol{e}_{l_q} - \boldsymbol{e}_{r_q + 1}) \end{align*}\]

そして, $D$ は同型写像になる. 実際, $D^{-1}: \mathcal{A} \to \mathcal{A}$ は以下を満たす線形写像となる.

\[D^{-1} \boldsymbol{e}_n = \sum_{k=0}^n \boldsymbol{e}_k\]

よって,

\[\boldsymbol{x} := \sum_{n=0}^\infty \alpha_n \boldsymbol{e}_n\]

とすると,

\[T_n D^{-1} \boldsymbol{x} = \sum_{k=0}^n \alpha_k\]

となる. 特に, $n \geq 1$ のときは

\[T_n D^{-1} \boldsymbol{x} = T_{n-1} D^{-1} \boldsymbol{x} + \alpha_n\]

となる. これはまさに $(T_n D^{-1} \boldsymbol{x})$ の累積和を表している式になる.

以上から,

\[\boldsymbol{y} := \sum_{q=1}^Q \left( \alpha_q \sum_{n={l_q}}^{r_q} \boldsymbol{e}_n \right)\]

は

\[\boldsymbol{x} := D \boldsymbol{y} = \sum_{q=1}^Q (\alpha_q \boldsymbol{e}_{l_q} - \boldsymbol{e}_{r_q + 1})\]

として, $\beta_n$ を $\beta_n := T_n \boldsymbol{x}$ で定めることによって,

\[T_n \boldsymbol{y} = \begin{cases} \beta_0 & (n = 0) \\ T_{n-1} \boldsymbol{y} + \beta_n & (n \geq 1) \end{cases}\]

で求められる.

Code

class Imos_1:
    def __init__(self, N: int):
        """ 区間 0 <= t < N に対する Imos 法のデータ構造を作成する.

        Args:
            N (int): 幅
        """

        self.__N = N
        self.list = [0] * (N + 1)

    def __len__(self):
        return len(self.list) - 1

    def add(self, l: int, r: int, x = 1):
        """ 閉区間 [l, r] に x を加算する.

        Args:
            l (int): 左端
            r (int): 右端
            x (int, optional): 追加する値. Defaults to 1.
        """

        if l > r:
            return

        if 0 <= l < self.__N:
            self.list[l] += x

        if 0 <= r < self.__N:
            self.list[r + 1] -= x

    def cumulative_sum(self):
        """ 累積和を求める
        """

        X = self.list.copy()[:-1]
        for i in range(1, len(self)):
            X[i] += X[i - 1]

        return X

#=================================================
from collections import defaultdict
class Sparse_Imos_1:
    def __init__(self):
        self.dict=defaultdict(int)

    def add(self, l, r, x=1):
        """閉区間 [l,r] に x を加算する.
        """

        if l<=r:
            self.dict[l]+=x
            self.dict[r+1]-=x

    def cumulative_sum(self, since, until):
        """累積和を求める.

        [Output]
        (y, l, r) という形のリスト. ただし, (y, l, r) は l<=x<=y の範囲では y であるということを意味する.
        """
        Y=[]
        S=0
        t_old=since
        dic=self.dict
        for t in sorted(dic):
            if t>until:
                break
            if dic[t]==0:
                continue

            if t_old<=t-1:
                Y.append((S, t_old,t-1))

            S+=dic[t]
            t_old=t

        if t_old<=until:
            Y.append((S, t_old,until))
        return Y

#=================================================
class Linear_Imos_1:
    def __init__(self, N):
        """ 区間 0<=t<N に対する Imos 法を準備する.
        """
        self.__N=N
        self.list=[0]*(N+2)

    def __len__(self):
        return len(self.list)-2

    def add(self, l, r, x=1):
        """閉区間 [l, r] に x を加算する."""

        assert 0<=l<self.__N
        assert 0<=r<self.__N

        self.add_linear(l,r,x,0)

    def add_linear(self, l, r, a, b):
        """ 閉区間 [l,r] に次のようにして加算する.
        I[l]+=a, I[l+1]+=a+b, I[l+2]+=a+2b, ..., I[t]+=a+(t-r)b, ...,  I[r]+=a+(r-l)b
        """

        assert 0<=l<self.__N
        assert 0<=r<self.__N

        if l<=r:
            self.list[l]+=a
            self.list[l+1]+=-a+b
            self.list[r+1]+=-a-(r-l+1)*b
            self.list[r+2]+=a+(r-l)*b

    def cumulative_sum(self):
        """累積和を求める.
        """
        X=self.list.copy()[:len(self)]
        for _ in range(2):
            for i in range(1,len(self)):
                X[i]+=X[i-1]
        return X

#=================================================
class Imos_2:
    def __init__(self,W,H):
        self.width=W
        self.height=H
        self.list=[[0]*(W+1) for _ in range(H+1)]

    def add(self, i0, j0, i1, j1, x=1):
        """ 閉区間 [i0, j0] x [i1,j1] に x を加算する.
        """

        self.list[i0][j0]+=x
        self.list[i0][j1+1]-=x
        self.list[i1+1][j0]-=x
        self.list[i1+1][j1+1]+=x

    def add_row(self, i, x):
        """ 第 i 行 (i, *) に x を加える."""
        self.add(i, 0, i, self.width-1, x)

    def add_column(self, j, x):
        """ 第 j 列 (*, j) に x を加える."""
        self.add(0, j, self.height-1, j, x)

    def cumulative_sum(self):
        Y=[self.list[i].copy()[:-1] for i in range(self.height)]

        for _ in range(2):
            for i in range(len(Y)):
                y=Y[i]
                for j in range(1,len(y)):
                    y[j]+=y[j-1]
            Y=[list(y) for y in zip(*Y)]
        return Y

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

Imos 法 (Imos.py)

Outline

Theory

Code

Imos 法
(Imos.py)