Sqrt-декомпозиция (корневая оптимизация)

Да, я тоже очень вдохновилась после этой лекции. Ощутила, что я на самом деле вообще нифига не шарю в структурах и деревьях (хотя до этого была другого мнения) (=

А других источников кроме e-maxx'а нет? А про КД-дерево и иже с ними? (=

В начале поста упомянута некая «идея, применимая к задачам другого типа». А, собственно, что за идея?

Хотел расписать одну задачу с которой недавно столкнулся, но статья затянулась…

Если я не ошибаюсь, такая статья уже была. Именно особенность с предварительным подсчётом сумм и квадратный корень мне запомнились.

Тем не менее, хорошо написано и +1.

Возможно Вашь алгоритм можно улучшить, в случае если L>=R. В случае если это условие выплняется, то sqrt суммы для R частично считать не нужно, они уже посчитаны для L.
Кроме того, если бы в статье были приведены примеры Unit тестов то материал был бы более усваиваем.

Та же идея применима к спискам с пропусками, если ограничить высоту списка двойкой. В этом случае легко показать, что оптимальным является расстановка узлов высоты два как раз через n^1/2 узлов нижнего уровня. Это гарантирует время поиска в списке порядка O(n^1/2). Более точно это время оценивается, как 2n^1/2. Идею можно развить, если ввести не два уровня, а например, три. Тогда оптимальным будет расположение «высоких» узлов через n^1/3 узлов каждого уровня. Этот даст нам время поиска порядка 3n^1/3. Если довести эти рассуждения до логического конца, то при k=log₂n уровнях (в этом случае получаются минимально возможные подмассивы длины два) получим время поиска равное 2log₂n — это кмк оптимальный результат полноценного списка с пропусками. И подозреваю, что такое же время будет у нормального дерева отрезков…