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