以下面的字符串作为一个例子：跟踪字符串中特定字符索引的最有效方法是什么？
“快速褐色fox”
眼下快速的q是在字符串（开始于0）和在狐狸的F指数4是在索引16.现在让我们说用户在这个字符串中输入更多的文本。
“很快的暗棕色狐狸”
现在q为指数9和f是在指数26
什么是保持原有的指数跟踪的最有效的方法无论用户添加了多少个字符，都可以在狐狸中迅速找到f？
语言并不重要，我，这是比什么理论问题的所以在使用任何一种语言，你只想尽量保持它普遍流行和目前使用的语言。
我给出的示例字符串很短，但我希望有一种方法可以高效地处理任何大小的字符串。所以使用偏移量更新数组可以使用短字符串，但会遇到许多字符。
尽管在示例中我正在寻找字符串中唯一字符的索引，我也希望能够跟踪不同位置的相同字符的索引，例如棕色中的o和狐狸中的o。所以搜索是不可能的。
我希望的答案是时间和内存使用效率，但如果我不得不选择只有一个我更关心的性能速度。
假设你有一个字符串，它的一些信件是有趣。为了让事情变得容易，让我们假设索引0处的字母总是很有趣，并且你从不在—之前添加一些东西。写下一对（有趣的字母，距离前一个有趣的字母）。如果字符串是“+非常快速的黑褐色狐狸”，并且您对'快速'和f'来自'狐狸'感兴趣，那么你会写:(+，0），（q，10），（f，17 ）。 （标志+是标志。）
现在，您将它们放在一个平衡的二叉树中，其顺序遍历按字符串出现的顺序给出顺序。您现在可能会认识到partial sums problem：您增强了树状结构，使节点包含（字母，距离，和）。总和是左子树中所有距离的总和。 （因此sum（x）= distance（left（x））+ sum（left（x））。）
您现在可以在对数时间内查询和更新此数据结构。
说，你加入ň字符，字符ç左边你说的距离（C）+ = N的，然后去为ç所有家长更新总和。
要问什么是Ç你计算总和（C）+ SUM（父（C））+总和指数（父（母（C）））+ ...
你的问题有点模棱两可 - 你想追踪每封信的第一个实例吗？如果是这样，一个长度为26的阵列可能是最好的选择。
当你插入文字比你有指数低的位置的字符串，只是计算基于插入的字符串的长度偏移。
如果你有一个目标语言的话，这也将有所帮助，因为并非所有的数据结构和交互在所有语言中都具有同样的效率和效率。
标准的把戏通常在类似情况下有助于将字符串的字符保留为平衡二叉树中的叶。此外，树的内部节点应该保留以特定节点为根的子树中出现的字母集合（如果字母小且固定，它们可能是位图）。
在此结构中插入或删除一个字母只需要O（log（N））操作（将路径上的位图更新为root）并查找字母的第一次出现也需要O（log（N））操作 - 你从根中下来，去找位图中包含有趣的字母的最左边的孩子。
编辑：内部节点也应该保留代表子树中的树叶数，以便高效计算字母索引。