# 什么是 rope

rope<char> 是针对大规模字符串拼接、分割、替换等操作进行优化的数据结构，通常底层以平衡树实现

# 使用方法

C++

// rope 不在万能头中，并且在 __gnu_cxx 命名空间
#include <ext/rope>
using namespace __gnu_cxx;

void solve () {
    rope<char> r1;                  // 默认空 rope
    rope<char> r2("hello world");   // 从字符串构造 rope
    rope<char> r3(r2);              // 拷贝构造，共享底层节点
    // r3[1] = 'a';    rope不支持直接 r[idx] = newChar，可以通过replace 来实现
    r3.replace(1, 1, rope<char>("*"));
    cout << r2[1];     // 修改 r3 时，r2 不会变化

    cout << r2[1] << '\n';              // 访问，输出 'e'
    cout << r2.size() << '\n';          // 求长度

    r1 = r2 + rope<char>("!!!");         // 拼接
    
    r1.insert(5, rope<char>("--"));         // .insert(idx, rope<char>("新字符串")) -> 在 idx 前，插入新字符串
    r1.erase(5, 2);                         // .erase(idx, len) -> 删除从 idx 开始的，len 个字符
    r1.replace(6, 5, rope<char>("***"));    // .replace(idx, len, rope<char>("新字符串")) -> 将从 idx 开始的，len 个字符，替换成新字符串
    rope<char> sub = r2.substr(6, 5);       // .substr(idx, len) -> 返回从 idx 开始的，长度为 len 的字符串构造而成的一个 rope<char>
}

# rope 和 string 的对比

操作	`string` 时间复杂度	`string` 空间复杂度	`rope<char>` 时间复杂度	`rope<char>` 空间复杂度
构造： `string(s)`	$O(N)$ （拷贝 $N$ 字符）	$O(N)$ （存储 $N$ 字符）	$O(N)$ （建立平衡树节点，或叶子数组）	$O(N)$ （树节点或叶子数组总共存储 $N$ 字符）
拷贝： `string t = s`	$O(N)$ （深拷贝所有字符）	$O(N)$ （新缓冲区 $N$ 字符）	$O(1)$ （共享根指针，写时复制延迟到修改时）	$O(1)$ （仅共享节点指针；修改时增量分配）
索引访问： `s[i]`	$O(1)$	$O(1)$	$O(log N)$	$O(1)$
长度： `s.size()`	$O(1)$	$O(1)$	$O(1)$	$O(1)$
拼接： `a + b`	$O(N+M)$ （分配新缓冲区并复制）	$O(N+M)$ （新缓冲区）	$O(log N + log M)$	$O(1)$ （仅创建一个新根节点）
追加： `a += b`	$O(M)$ （摊还摊销，必要时复制 $N$ ）	$O(M)$ （必要时扩容）	$O(log N + log M)$	$O(1)$ （节点指针重组；叶子分配增量）
插入： `s.insert(i,b)`	$O(N + M)$ （移动尾部 + 复制 $b$ ）	$O(M)$ （存储 b）	$O(log N + log M)$	$O(1)$ （分裂 / 合并节点，增量分配 $b$ ）
删除： `s.erase(i,len)`	$O(N)$ （移动尾部）	$O(1)$ （就地移位）	$O(log N)$	$O(1)$ （分裂 / 丢弃子树）
替换： `s.replace(i,len,b)`	$O(N + M)$ （移位 + 复制 $b$ ）	$O(M)$	$O(log N + log M)$	$O(1)$ （分裂 / 合并 + 增量分配 $b$ ）
子串： `s.substr(i,len)`	$O(len)$ （复制 $len$ 字符）	$O(len)$	$O(log N)$	$O(1)$ （共享对应子树，只读）

rope<char> 的缺点在于

难以做到单点修改（可用 replace 替代）
返回整个字符串困难，只能通过遍历输出
只存在于 $GCC$ 的 $libstdc++$ 扩展中， $Clang$ 默认的 $libc++／MSVC$ 均不支持，如果比赛要用的话，一定要看清楚，提供的环境是什么！！！

数据结构 rope