繩索數據結構權重是節點中的字符加左子樹或左右子樹的權重？

Question

維基百科entry說：

每個節點的「權重」等於其字符串的長度加上左子樹中所有權重的總和。因此，有兩個子節點的節點將整個字符串分爲兩部分：左子樹存儲字符串的第一部分。右子樹存儲第二部分，它的權重是兩部分的總和。

我有點困惑，它首先說節點權重是其字符串的長度加上左子樹中所有權重的總和。然後它說如果一個節點有兩個孩子（因此有一個左子樹和一個右子樹），則權重是兩個子樹的總和，而不僅僅是左子樹。看圖是有道理的（直接在22以下的9是9而不是更大，因爲7的正確的子/子樹不會影響重量），但是這些措辭對我來說似乎還是或者我誤解了某些東西？

Answer 1

是的，該措辭是關閉的。 「weight」是分區點，所以它只包含左邊的子字符串（或者包含的字符串，如果這就是你所擁有的字符串）。

你並不需要存儲節點的總長度，但修改繩要求所有的父節點被更改的通知（這應該是O（log n）的，所以這是好的。）