平衡树 Rope

声明

rope 最初是作为字符串的存储结构，对字符类型有优化 crope。但同时他也支持泛型编程（可比较类型或小于号重载，与上述 Tree 相同），一般来说，使用rope 来进行声明，你可以将他理解为一个增强版的 vector。

用法

1. 基本操作

   方法	说明	时间复杂度
   rope r / crope r	构造空 rope	$O(1)$
   crope r("text")	使用字符串构造	$O(n)$
   r.push_back(c)	在末尾添加字符	$O(\log n)$
   r.insert(pos, str)	在位置 pos 插入字符串	$O(\log n + m)$
   r.erase(pos, len)	从 pos 开始删除 len 个字符	$O(\log n)$
   r.replace(pos, str)	从 pos 开始替换为字符串	$O(\log n + m)$
   r.substr(pos, len)	从 pos 开始截取 len 个字符	$O(\log n + len)$
   r.append(str)	在末尾追加字符串	$O(\log n + m)$
   r.clear()	清空所有内容	$O(n)$
   r = r1 + r2	连接两个 rope	$O(\log n + \log m)$

2. 访问与遍历

   方法	说明	时间复杂度
   r[i]	访问第 i 个字符（无边界检查）	$O(\log n)$
   r.at(i)	访问第 i 个字符（有边界检查）	$O(\log n)$
   r.begin(), r.end()	返回正向迭代器	$O(1)$
   r.rbegin(), r.rend()	返回反向迭代器	$O(1)$
   r.c_str()	转换为 C 风格字符串	$O(n)$

3. 容量与信息

   方法	说明	时间复杂度
   r.size()	返回字符数量	$O(1)$
   r.length()	返回字符数量（同 size）	$O(1)$
   r.empty()	判断是否为空	$O(1)$
   r.max_size()	返回最大可能大小	$O(1)$

4. 查找与比较

   方法	说明	时间复杂度
   r.find(str, pos)	从 pos 开始查找字符串（实现依赖）	$O(n + m)$
   r.compare(pos, len, str)	与字符串比较	$O(len)$
   ==, !=, <, > 等	关系运算符	$O(\min(n, m))$

5. 特殊操作

   方法	说明	时间复杂度
   r.copy(pos, len, str)	复制到字符串 str	$O(len)$
   swap(r1, r2)	交换两个 rope 内容	$O(1)$
   r.reserve(size)	预留空间（实现依赖）	实现相关
   r.capacity()	返回当前容量（实现依赖）	$O(1)$

6. 迭代器操作

   方法	说明	时间复杂度
   r.begin() + n	前进 n 个位置	$O(\log n)$
   r.end() - n	后退 n 个位置	$O(\log n)$
   distance(it1, it2)	计算迭代器间距离	$O(\log n)$
   advance(it, n)	迭代器前进 n 步	$O(\log n + |n|)$

适用场景

Problem - Code