Блог

В этих источниках cp-algorithms и geeksforgeeks указано, что сложность запроса (например, сумма подматриц) двумерного дерева сегментов равна O (logN * logM), потому что

сначала он спускается по дереву по первой координате и для каждой пройденной вершины этого дерева выполняет запрос из обычного дерева сегментов по второй координате

Однако во всех реализациях, с которыми я встречался, запрос спускается по дереву по второй координате только тогда, когда он достигает некоторого узла первого дерева (не может повторяться дальше). Далее, поскольку во время запроса выполняется не более 4 рекурсивных вызовов на уровень дерева сегментов, всего по второй координате будет не более 4 запросов. Итак, на мой взгляд, временная сложность должна быть O (logN logM). Что я упускаю?