Как мы можем вычислить взвешенную сумму префикса с обновлениями диапазона префиксов? - PullRequest
0 голосов
/ 09 апреля 2020

Учитывая массив A с n элементами, который начинается со всех 0 s, а другой массив W также с n элементами (все больше чем 0), мы хотим выполнить следующую операцию несколько раз;

Для данного k, приращение A[0], A[1], .... A[k] каждый на 1; сообщить значение A[0] * W[0] + A[1] * W[1] + ... + A[k-1] * W[k-1].

Поиск решения O(log n) или более быстрого для каждого запроса. Возможно O(n log n) обработка необходима.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...