対数時間ランダムアクセス/挿入/削除可能リスト (スプレー木)
(DataStructure/List/SplayTreeList.py)

• View this file on GitHub
• Last update: 2022-01-23 04:17:44+09:00

概要

要素のランダムアクセス、挿入、削除を $\mathrm{amortized}\ O(\log N)$ で行えるリスト。

使い方

SplayTreeList()
空のリストを作成する。計算量 $O(1)$

• __getitem__(i: int) -> int
  $i$ 番目の要素を返す。計算量 $\mathrm{amortized}\ O(\log N)$

• __setitem__(i: int, val: int) -> None
  $i$ 番目の要素に val を代入する。計算量 $\mathrm{amortized}\ O(\log N)$

• __len__() -> int
  リストの長さを返す。計算量 $O(1)$

• insert(i: int, val: int) -> None
  $i$ 番目の位置に val を挿入する。計算量 $\mathrm{amortized}\ O(H + \log N)$

• delete(i: int) -> None
  $i$ 番目の要素を削除する。計算量 $\mathrm{amortized}\ O(\log N)$

Verified with

• TestCase/AOJ/ITP2_1_C.SplayTree.test.py

Code

class STNode:
    def __init__(self, val):
        self.val = val
        self.l, self.r, self.p = None, None, None
        self.size = 1

    def update(self):
        self.size = 1
        if self.l is not None: self.size += self.l.size
        if self.r is not None: self.size += self.r.size

    def state(self):
        if self.p is None: return 0
        if self.p.l == self: return 1
        else: return -1  # self.p.r == self

    def splay(self):
        while self.p is not None:
            st, st_p = self.state(), self.p.state()
            if st_p == 0:
                if st == 1: self.p._rotr()
                else: self.p._rotl()
            elif st_p == 1:
                if st == 1:
                    self.p.p._rotr()
                    self.p._rotr()
                else:
                    self.p._rotl()
                    self.p._rotr()
            else:
                if st == 1:
                    self.p._rotr()
                    self.p._rotl()
                else:
                    self.p.p._rotl()
                    self.p._rotl()
        return self

    def _rotl(self):
        nd = self.r
        nd.p = self.p
        if nd.p is not None:
            if nd.p.l is self: nd.p.l = nd
            else: nd.p.r = nd
        self.r = nd.l
        if self.r is not None: self.r.p = self
        self.p = nd
        nd.l = self
        self.update()
        nd.update()

    def _rotr(self):
        nd = self.l
        nd.p = self.p
        if nd.p is not None:
            if nd.p.r is self: nd.p.r = nd
            else: nd.p.l = nd
        self.l = nd.r
        if self.l is not None: self.l.p = self
        self.p = nd
        nd.r = self
        self.update()
        nd.update()


class SplayTreeList:
    def __init__(self):
        self.root = None

    def __getitem__(self, idx):
        self._splay(idx)
        return self.root.val

    def __setitem__(self, idx, val):
        self._splay(idx)
        self.root.val = val

    def __len__(self):
        return self.root.size if self.root is not None else 0

    def _splay(self, idx):
        nd = self.root
        while True:
            sizel = nd.l.size if nd.l is not None else 0
            if idx < sizel: nd = nd.l
            elif idx > sizel:
                nd = nd.r
                idx -= sizel + 1
            else:
                self.root = nd.splay()
                break

    def _merge(self, rtl, rtr):
        if rtl is None: return rtr
        if rtr is None: return rtl
        while rtl.r is not None:
            rtl = rtl.r
        rtl = rtl.splay()
        rtl.r = rtr
        rtr.p = rtl
        rtl.update()
        return rtl

    def _split(self, cntl):
        if cntl == 0: return None, self.root
        if cntl == self.root.size: return self.root, None
        self._splay(cntl)
        rtl = self.root.l
        rtr = self.root
        rtl.p = None
        rtr.l = None
        rtr.update()
        return rtl, rtr

    def insert(self, idx, val):
        rtl, rtr = self._split(idx)
        rt = STNode(val)
        self.root = self._merge(self._merge(rtl, rt), rtr)

    def delete(self, idx):
        self._splay(idx)
        rtl = self.root.l
        rtr = self.root.r
        if rtl is not None: rtl.p = None
        if rtr is not None: rtr.p = None
        self.root = self._merge(rtl, rtr)

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