Day 142-Q2 | Rope

問題

小文字英字からなる文字列 $S$（長さ $N$）が与えられる。続けて $Q$ 個のクエリが与えられ、各クエリは以下の3種類のいずれかである。

1 p c: 0-indexedで位置$p$の直前に文字$c$を挿入
2 p: 0-indexedで位置$p$の文字を削除
3 l r: 現在の文字列の区間$[l,r)$（0-indexed、$r$は含まない）を出力

単純にPythonの文字列を毎回スライスして作り直すと1クエリあたり$O(N)$かかり間に合わない。Rope（Treapを用いた暗黙的な分割・結合構造）を使い各クエリを期待$O(\log N)$で処理すること。

入力形式

N Q
S
query_1
:
query_Q

制約

$1 \le N \le 2\times10^5$

$1 \le Q \le 2\times10^5$

文字列長は常に1以上を保つ

位置指定はクエリ処理時点で常に有効な範囲内

入出力例

入力例1

出力例1

abXcde
abXcd

概念図

ヒント（段階的開示）

ヒント1（方向性）

配列の「$k$番目の要素」は、二分探索木で「左部分木のサイズ」を管理していれば木構造だけで表現できる。これが暗黙Treapであり、キーの代わりに木の形（中順走査の並び）そのものが配列の順序を表す。この考え方に基づくと文字列の任意位置での分割・結合が$O(\log N)$になる。

ヒント2（アプローチ）

split(t,k): 木$t$を先頭$k$文字と残りの2本に分割。merge(a,b): 2本の木をこの順序を保って1本に結合。挿入は「splitして単一文字ノードを挟んでmerge」、削除は「splitして1文字分だけさらにsplitし切り離す」、部分文字列取得は「2回splitして中順走査」ですべて表現できる。

ヒント3（誘導）

def split(t, k):
    if t is None:
        return None, None
    if size(t.l) < k:
        l, r = split(t.r, k - size(t.l) - 1)
        t.r = l; pull(t)
        return t, r
    else:
        l, r = split(t.l, k)
        t.l = r; pull(t)
        return l, t

def merge(a, b):
    if a is None: return b
    if b is None: return a
    if a.pri > b.pri:
        a.r = merge(a.r, b); pull(a); return a
    else:
        b.l = merge(a, b.l); pull(b); return b

優先度priをランダムに振ることで木の高さを期待$O(\log N)$に保つ（Treapのバランス機構）。

模範解答 (Python)

import sys
import random

class Node:
    __slots__ = ("ch", "pri", "sz", "l", "r")
    def __init__(self, ch):
        self.ch = ch
        self.pri = random.random()
        self.sz = 1
        self.l = None
        self.r = None

def size(t):
    return t.sz if t else 0

def pull(t):
    t.sz = 1 + size(t.l) + size(t.r)

def split(t, k):
    if t is None:
        return None, None
    if size(t.l) < k:
        l, r = split(t.r, k - size(t.l) - 1)
        t.r = l
        pull(t)
        return t, r
    else:
        l, r = split(t.l, k)
        t.l = r
        pull(t)
        return l, t

def merge(a, b):
    if a is None:
        return b
    if b is None:
        return a
    if a.pri > b.pri:
        a.r = merge(a.r, b)
        pull(a)
        return a
    else:
        b.l = merge(a, b.l)
        pull(b)
        return b

def build(s):
    root = None
    for c in s:
        root = merge(root, Node(c))
    return root

def to_str(t, out):
    if t is None:
        return
    to_str(t.l, out)
    out.append(t.ch)
    to_str(t.r, out)

def insert_at(root, pos, c):
    l, r = split(root, pos)
    return merge(merge(l, Node(c)), r)

def delete_at(root, pos):
    l, r = split(root, pos)
    mid, r2 = split(r, 1)
    return merge(l, r2)

def substr(root, l, r):
    a, b = split(root, l)
    c, d = split(b, r - l)
    out = []
    to_str(c, out)
    root2 = merge(merge(a, c), d)
    return "".join(out), root2

def main():
    random.seed(12345)
    data = sys.stdin.read().split("\n")
    idx = 0
    n, q = map(int, data[idx].split()); idx += 1
    s = data[idx]; idx += 1
    root = build(s)
    res = []
    for _ in range(q):
        parts = data[idx].split(); idx += 1
        if parts[0] == "1":
            p, c = int(parts[1]), parts[2]
            root = insert_at(root, p, c)
        elif parts[0] == "2":
            p = int(parts[1])
            root = delete_at(root, p)
        else:
            l, r = int(parts[1]), int(parts[2])
            out, root = substr(root, l, r)
            res.append(out)
    print("\n".join(res))

main()

Step-by-Step 解説

1splitの仕組み
左部分木のサイズがkより小さければ根とその左部分木は「先頭k個」側に確定し、右部分木を再帰的に分割する。逆にk以上なら根は「残り」側に回る。再帰は木の高さ分、期待$O(\log N)$。

2mergeの仕組み
優先度が高い方を根にしながら結合する。優先度はランダムに振られているため結合後の木の高さも期待$O(\log N)$に保たれる。

3挿入・削除・部分文字列取得
挿入は「split→単一文字を挟んでmerge」、削除は「split→さらに1文字split→merge」、部分文字列取得は「2回splitして中順走査、その後merge で戻す」。

4Pythonのstr直接操作が遅い理由
immutableな文字列へのs[:p]+c+s[p:]は毎回$O(N)$。$Q$回のクエリで最悪$O(NQ)$になり間に合わない。

5計算量
初期構築は期待$O(N\log N)$、各クエリは期待$O(\log N)$。全体で期待$O((N+Q)\log N)$。

よくあるミス

ミス	原因	正しい書き方
split後にpullを呼び忘れszが更新されない	子を書き換えたのにサイズ情報を再計算していない	子を書き換えたノードでは必ずpull(t)を呼ぶ
部分文字列取得後に木をmergeで戻し忘れ以降のクエリで文字列が欠落する	splitで切り出した3つの木をそのまま放置	読み取り目的でも必ずmergeで結合し直しrootを更新
random.random()の優先度衝突を心配しすぎ複雑な処理を入れる	浮動小数点の優先度は実用上ほぼ衝突しない	シンプルにrandom.random()を使えばよい
削除クエリでsplit(r,1)を忘れ2文字以上切り離してしまう	削除は1文字だけを取り除く操作であることを見落とす	必ずsplit(r,1)で1文字分だけ切り出す
再帰深さがO(N)になり得ると誤解する	Treapは優先度で高さが期待O(log N)に保たれると理解していない	優先度をランダムに振っている限り期待O(log N)が保証される

次のステップ

発展: reverse(l, r)クエリを遅延伝播フラグで$O(\log N)$で追加せよ（Day131-Q4のFHQ Treapとも関連）。
発展2: 2つの独立した文字列に対しconcat/splitを外部から呼べるインターフェースを整備し、テキストエディタのUndo/Redoのような永続化にも対応させよ。

自己評価

完全理解おおむね理解要復習

Day 142-Q2 — Rope（Treapベース分割/結合文字列によるO(log N)編集）

問題