Доказательство сложности времени для реализации дерева ранжированных сумм в дереве сегментов

10

Я понимаю , что сегментные дерева могут быть использованы , чтобы найти сумму юга массива . И что это может быть сделано за O ( log n ) в соответствии с руководством здесь .AO(logn)

Однако я не могу доказать, что время запроса действительно равно . Эта ссылка (и многие другие) говорят, что мы можем доказать, что на каждом уровне максимальное количество обрабатываемых узлов равно 4, и поэтому O ( 4 log n ) = O ( log n ) .O(logn)4O(4logn)=O(logn)

Но как мы можем доказать это, возможно, противоречием?

И если так, если бы мы использовали деревья сегментов для ранжированной суммы массивов более высокой размерности, как доказательство было бы расширено?

Например, я могу подумать о поиске суммы подматрицы путем деления исходной матрицы на 4 квадранта (аналогично интервалам деления пополам в линейных массивах), построения дерева сегментов квадранта, но доказательство ускользает от меня.

Ариджит Чоудхури
источник
построение дерева сегментов O (n), запрос O (log n) и обновление O (log N). Преимущество по сравнению с массивом sum заключается в сложности обновления.
Нурлан

Ответы:

11

2

Рассмотрим дерево сегментов, приведенное ниже.

Сегментное дерево

32logn2logn=Θ(logn)

adijo
источник