Середина
Проблема
Для массива целых чисел nums найдите сумму элементов между индексами i и j (i ≤ j) включительно.
Функция update(i, val) изменяет nums, обновляя элемент с индексом i до val.
Пример:
Given nums = [1, 3, 5] sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8
Примечание.
- Массив можно изменить только с помощью функции update.
- Можно предположить, что количество вызовов функций update и sumRange распределено равномерно.
Решение — дерево сегментов
Он достигнет предела времени, если мы будем использовать подход грубой силы, который каждый раз суммирует каждый элемент в заданном диапазоне запроса. Это займет O (n) для каждого запроса и потеряет слишком много времени.
Применение подхода Дерево сегментов позволяет значительно сократить операции update и query.
Сложность
Поскольку количество узлов в дереве сегментов равно 2n, а мы обновляем n узлов одновременно, для построения дерева сегментов потребуется O(n) время, если n означает количество узлов в заданном списке nums.
Для операций update и query обе они обновляют узлы на пути от корня к листу, поэтому их временная сложность будет равна O(logn).
Решение — двоичное индексированное дерево
Он также известен как Дерево Фенвика с меньшим объемом манипуляций и выделением памяти. Кроме того, это проще в реализации.
Сложность
Для операций update и query они оба манипулируют текущим узлом и всеми его родительскими/дочерними узлами, поэтому их временная сложность будет O(logn), если n означает количество узлов в данном nums.
И согласно этому посту мы можем построить тебя за O(n) времени.
