Вес структуры данных веревки - это символы в узле плюс вес левого поддерева или левого и правого поддеревьев?

Question

Запись в Википедии гласит:

Каждый узел имеет "вес", равный длине его строки плюс сумма всех весов в его левом поддереве. Таким образом, узел с двумя дочерними элементами делит всю строку на две части: левое поддерево хранит первую часть строки. Правое поддерево хранит вторую часть, а его вес является суммой двух частей.

Я немного сбит с толку, сначала он говорит, что вес узла - это длина его строки плюс сумма всех весов в его левом поддереве. Затем он говорит, что если у узла есть два дочерних элемента (и, следовательно, левого и правого поддерева), то вес является суммой обеих частей, а не только левого поддерева. Глядя на диаграмму имеет смысл (9 непосредственно под 22 - это 9, а не больше, потому что правильный ребенок / поддерево 7 не влияет на вес), но мне кажется, что формулировка не подходит или я что-то неправильно понимаю?

Answer 1

Да, формулировка выключена. "Вес" - это точка разбиения, поэтому она включает только левую подстроку (или включенную строку, если она у вас есть).

Вам не нужно хранить общую длину узла, но для изменения веревки необходимо, чтобы все родительские узлы были уведомлены об изменении (это должно быть O(log n), так что все в порядке).