Rope

A balanced binary tree over a string. Leaves hold short chunks; each internal node stores weight = characters in its left subtree. Index descends by weight (O(log n)); concat just makes a parent (O(1)); split partitions one path (O(log n)).

Index: O(log n) Concat: O(1) Split: O(log n) Insert/Delete: O(log n) Space: O(n)
Build
Index i
Split at
Concat +
Speed
Internal (weight)
Leaf (chunk)
On descent path
Target / left result
New node

Info Panel

Build a rope, then run Index / Split / Concat to watch the descent.

Stats

n (chars)
0
Leaves
0
Height
0
Nodes visited
0
Result
-

Big-O

OperationTimevs Flat string
Index char iO(log n)O(1)
Concat A+BO(1)O(a+b)
Split at iO(log n)O(n)
Insert / DeleteO(log n)O(n)
Substring (m)O(log n + m)O(m)
SpaceO(n)O(n)

Operation Log

Weight of a node = number of characters in its left subtree. Index: if i < weight go left, else i −= weight and go right. Concat builds a parent (no characters copied). Split partitions one root-to-leaf path. Balancing (treap / AVL / rebuild) keeps height O(log n) — see senior/professional.md.