Я понимаю , что сегментные дерева могут быть использованы , чтобы найти сумму юга массива . И что это может быть сделано за O ( log n ) в соответствии с руководством здесь .
Однако я не могу доказать, что время запроса действительно равно . Эта ссылка (и многие другие) говорят, что мы можем доказать, что на каждом уровне максимальное количество обрабатываемых узлов равно 4, и поэтому O ( 4 log n ) = O ( log n ) .
Но как мы можем доказать это, возможно, противоречием?
И если так, если бы мы использовали деревья сегментов для ранжированной суммы массивов более высокой размерности, как доказательство было бы расширено?
Например, я могу подумать о поиске суммы подматрицы путем деления исходной матрицы на 4 квадранта (аналогично интервалам деления пополам в линейных массивах), построения дерева сегментов квадранта, но доказательство ускользает от меня.
источник
Ответы:
Рассмотрим дерево сегментов, приведенное ниже.
источник