設計MutableString

嗨各路大神～
   这是一道pocket gem的面经题，设计MutableString，看过去面经，有人说面试官说可以用tree结构完成，但是还是毫无头绪，希望各路大神能提点，若是能分享代码更是感激。
題目如下：
  Design a string class , with implementation of charAt() and substring(b,e), with substring() requires O(1) time and O(1) space complexity
followup:
a new method setCharat(index, char) is added, a substring must keep the changes of parrent string that are made before its creation, but both the parent string and the substring will not affect each other after the creation of the substring, requires O(1) space complexity