Disjoint Sparse Table
(Disjoint_Sparse_Table.py)

• View this file on GitHub
• Last update: 2023-03-20 03:47:37+09:00
• Link: https://ei1333.github.io/library/structure/others/disjoint-sparse-table.cpp.html

Outline

半群 $S=(S, *)$ の列 $A=(A_0, A_1, \dots, A_{\lvert A \rvert-1})$ に対して, 区間積 $A_L * \dots * A_R$ の計算を $O(1)$ Time で行うことができるデータ構造.

ただし, 区間積を $O(1)$ Time で計算できる代償として, 更新ができない.

Constructer

T=Disjoint_Sparse_Table(A, calc)

• $A$ : $S$ の列

以下, $N:=\lvert A \rvert$ とする.

• $\operatorname{calc} : S \times S \to S; (x,y) \mapsto x * y$ : 二項演算
• 計算量 : $O(N \log N)$ Time.

---

product

T.product(l, r, default=None, left_close=True, right_close=True)

• 区間積 $A_L * A_{L+1} * \dots * A_R$ を求める. なお, $L>R$ の場合は default を返す.
• なお, left_close , right_close を False とすると, それぞれに対応する方が開区間 (端点が含まれない) になる.
• 制約
  • $0 \leq L \lt N$
  • $0 \leq R \lt N$
• 計算量 : $O(1)$ Time.

Verified with

• test_verify/yosupo_library_checker/Data_Structure/Disjoint_Sparse_Table.test.py

Code

class Disjoint_Sparse_Table:
    """ 参考: https://ei1333.github.io/library/structure/others/disjoint-sparse-table.cpp.html """

    def __init__(self, L, op):
        """ L の演算 op に対する Disjoint Sparse Table を生成する.

        L: list
        op: 二項演算
        """

        self.op=op
        self.size=N=len(L)
        self.b=max(1,(N-1).bit_length())

        self.table=[[0]*self.size for _ in range(self.b)]

        tab=self.table[0]
        for i in range(self.size):
            tab[i]=L[i]

        shift=1
        for i in range(1,self.b):
            shift<<=1
            tab=self.table[i]

            for j in range(0,N,2*shift):
                t=min(j+shift,N)
                tab[t-1]=L[t-1]

                for k in range(t-2,j-1,-1):
                    tab[k]=op(L[k],tab[k+1])

                if N<=t:
                    break

                tab[t]=L[t]
                r=min(t+shift,N)

                for k in range(t+1,r):
                    tab[k]=op(tab[k-1],L[k])

    def product(self, l, r, default=None, left_close=True, right_close=True):
        """ l<=i<=r に対する積を生成する.

        """

        if not left_close:
            l+=1

        if not right_close:
            r-=1

        if l==r:
            return self.table[0][l]
        elif l>r:
            return default

        p=(l^r).bit_length()-1
        tab=self.table[p]
        return self.op(tab[l], tab[r])

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

Back to top page