Найти сумму всех элементов массива, исключая индексы от L до R
У нас есть массив arr[0 . . . n-1], Мы должны быть в состоянии
- Найти сумму элементов из индекса L в R, где 0 <= L <= R <= n-1.
- Изменить значение указанного элемента массива
arr[i] = xгде 0 <= я <= n-1.
Это может быть эффективно решено с помощью дерева сегментов.
Но как решить противоположное этому, т.е.
- Найти сумму всех элементов (arr [i]) от индекса 0 до n-1, исключая L<= я <= R, где L и R даны.
- Изменить значение указанного элемента
array arr[i] = xгде 0 <= я <= n-1.
Как эффективно решить вышеуказанный вопрос, как дерево сегментов?
Решение
Предполагая, что вы можете легко вычислить сумму (L, R) с помощью дерева сегментов.
Сначала вычислите общую сумму всего массива, названного total,
Для изменения в arr в положении ih
-
Обновите дерево сегментов как обычно.
-
Обновить
total = total - oldValue + newValue,
Для каждого запроса выведите total - sum(L,R)
Примечание: мы можем использовать двоичное индексированное дерево (a.k.a Дерево Фенвика) для этой проблемы тоже, которая ИМО, больше подходит.
Другие решения