Dual Segment Tree
(Segment_Tree/Dual_Segment_Tree.py)

• View this file on GitHub
• Last update: 2023-07-08 23:14:20+09:00

Outline

モノイド $F=(F, \circ, 1_F)$ の列に対する区間更新, 1点取得を得意とするデータ構造

Contents

---

Constructer

S=Dual_Segment_Tree(L, comp, id)

• $L$ : $M$ の列

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

• $\mathrm{comp} : F \times F \to F; (\alpha, \beta) \mapsto \alpha \circ \beta$ : 二項演算.
• $\mathrm{id}$ : $F$ の単位元 $1_F$.
• 計算量 : $O(N)$ Time.
• (※ 現在, $L$ は無効である)

---

operate

S.operate(self, l, r, alpha, left_closed=True, right_closed=True)

• 第 $l$ 要素から第 $r$ 要素全てに対して, 左から $\alpha$ を作用させる.
• left_close=False にすると, 左側が開区間になる (つまり, 左端が含まれなくなる). right_close についても同様.
• 制約
  • 作用させる区間を $I$ としたとき, $I$ は $[0,N)$ に含まれる.
  • $\alpha \in F$
• 計算量 : $O(\log N)$ Time.

---

get

S.get(k)

• 第 $k$ 要素を返す.
• 制約
  • $0 \leq k \lt N$
• 計算量 : $O(\log N)$ Time.

---

refresh

B.refresh()

• 更新を遅延していた作用の記録を全て更新する.
• 計算量 : $O(N \log N)$ Time.

Verified with

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

Code

class Dual_Segment_Tree:
    def __init__(self, L, comp, id):
        """ comp を演算とするリスト L の Dual Segment Tree を作成

        comp : 作用素
        id : 単位元

        [注記]
        更新は左から. つまり, comp(new, old) となる.
        """

        self.comp=comp
        self.id=id

        N=len(L)
        d=max(1,(N-1).bit_length())
        k=1<<d

        self.lazy=[self.id]*k+L+[self.id]*(k-N)
        self.N=k
        self.depth=d

    #配列の第 m 要素を下に伝搬
    def _propagate_at(self,m):
        lazy=self.lazy
        if lazy[m]!=self.id:
            lazy[(m<<1)|0]=self.comp(lazy[m],lazy[(m<<1)|0])
            lazy[(m<<1)|1]=self.comp(lazy[m],lazy[(m<<1)|1])
            lazy[m]=self.id

    #配列の第 m 要素より上を全て伝搬
    def _propagate_above(self,m):
        H=m.bit_length()
        for h in range(H-1,0,-1):
            self._propagate_at(m>>h)

    #作用
    def action(self, l, r, alpha, left_closed=True, right_closed=True):
        L=l+self.N+(not left_closed)
        R=r+self.N+(right_closed)

        L0=R0=-1
        X,Y=L,R-1
        while X<Y:
            if X&1:
                L0=max(L0,X)
                X+=1

            if Y&1==0:
                R0=max(R0,Y)
                Y-=1

            X>>=1
            Y>>=1

        L0=max(L0,X)
        R0=max(R0,Y)

        self._propagate_above(L0)
        self._propagate_above(R0)

        lazy=self.lazy; comp=self.comp
        while L<R:
            if L&1:
                lazy[L]=comp(alpha, lazy[L])
                L+=1

            if R&1:
                R-=1
                lazy[R]=comp(alpha, lazy[R])

            L>>=1
            R>>=1

    #リフレッシュ
    def refresh(self):
        for m in range(1,self.N):
            self._propagate_at(m)

    #取得
    def get(self,k):
        m=k+self.N
        self._propagate_above(m)
        return self.lazy[m]

    def __getitem__(self,index):
        m=index+self.N
        self._propagate_above(m)
        return self.lazy[m]

    def __setitem__(self,index,value):
        self.action(index, index, value)

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