Двоичное дерево, в котором хранятся частичные суммы: имя и существующие реализации

Рассмотрим последовательность n положительные действительные числа ( a _i ) и его последовательность частичных сумм ( s _i ). Дано число x ∊ (0, s _n ], мы должны найти i такое, что s _{i −1} < x ≤ с _и . Также мы хотим иметь возможность изменять один из a _i без необходимости обновлять все частичные суммы. И то, и другое можно сделать за O (log n ) времени, используя двоичное дерево с a _i в качестве значений конечных узлов и значениями нелистовых узлов. узлы, являющиеся суммой значений соответствующих дочерних элементов. Если n известно и зафиксировано, дерево не обязательно должно быть самобалансирующимся и может эффективно храниться в линейном массиве. Кроме того, если n является степенью двойки, требуется только 2 n -1 элементов массива. См. Blue et al., Phys. Ред. E 51 (1995), стр. R867 – R868 для приложения. Учитывая универсальность проблемы и простоту решения, Интересно, имеет ли эта структура данных определенное имя и существуют ли существующие реализации (желательно на C ++). Я уже реализовал это сам, но написание структур данных с нуля всегда кажется мне изобретением колеса - я был бы удивлен, если бы никто этого не делал раньше.