Что мы называем динамической программной конструкцией, которая позволяет нам вычислять суммы любого диапазона в логарифмическом времени?
Я обычно называл это "частичными суммами", но я не знаю, как это "официально" называется, и у меня сложилось впечатление, что это не "частичные суммы".
Во всяком случае, концепция довольно проста. Скажем, у вас есть массив 8 элементы, [3, 7, 2, 1, 5, 6, 9, 4], Вы вычисляете суммы следующим образом:
Конечно, это приведет к массиву массивов этой формы:
Теперь, если нас спросят, например, какова сумма элементов индексов из 0 до 4 мы не будем линейно вычислять эту сумму, но вместо этого мы будем знать, что она равна сумме элементов из 0 до 3 (который 13), а затем логарифмически идти вниз до элемента 5, Итак, ответ: 18,
Как мне назвать такую конструкцию, чтобы другие люди знали, о чем я говорю, без рисования таких таблиц?
2 ответа
Кажется, что некоторые разделы.
Хранение накопленных сумм позволяет вычислять сумму последовательных элементов за постоянное время и занимает тот же объем памяти (n). Пусть i-й элемент C будет суммой всех элементов с индексом <= i. Чем сумма элементов из индекса a до индекса b является C[b] - C[a],
Оно называется деревом сегментов и обычно используется для более быстрой обработки запросов.