Sqrt-декомпозиция

[@Flux]

Не хочется сходу обвинять автора в отсутствии фантазии, но чем данная статья отличается от, например, этой?

[@satellitez]

Я даже не подозревал о существовании такой статьи. Мой топик был на писан с лекции, которую я прослушал много лет назад.

[@general]

Для, именно вами указанной, постановки задачи оптимальным будет алгоритм, когда мы в D[i] заносим сумму длин отрезков с 0 по i. И ответ считаем как D[r]-D[l-1].

Ваше решение имеет право на жизнь, если изменение элементов массива происходит довольно часто, но не чаще чем «корень из n» изменений на одно считывание. Иначе полный пересчет опять становится эффективнее.

[@karlicos]

По идее, это работает для любой ассоциативной операции — минимума, например.

[@karlicos]

еще оно хорошо тем, что легко можно добавить еще одну операцию — изменение на отрезке, например.

[@orionll]

Ваш метод с D[i] выигрывает, если изменение элементов массива A происходит редко, потому что при каждом изменении элемента j приходится пересчитывать все D[i], у которых i >= j. А «авторский» метод более универсален.

Короче говоря, постановки задачи — расплывчатая, т.к. сильно зависит от частоты изменения/удаления элементов массива. Если например, элементы массива изменяются в 1000 раз чаще, чем считается эта пресловутая сумма от l до r, то выгоднее вообще не содержать никакого массива B, а тупо суммировать простым циклом от l до r.

[@xni]

Одному мне мерещится массив из 1 000 000 элементов и постоянные запросы на частичную сумму из 999 слагаемых?

[@darnley]

Второе предложение в статье:

> «… это древо отрезков(RSQ), но он довольно сложен в написании и понимании»

Оба утверждения не верны.

RSQ — это Range Sum Query. Это вовсе не дерево отрезков, а задача, которую Вы решаете (запросы о сумме на отрезке).

И сложного ничего нет ни в написании, ни в понимании дерева отрезков.
Как раз сегодня (ирония detected!) мой коллега рассказал школьникам на кружке (8—10 класс) дерево отрезков за одно занятие без проблем.

[@satellitez]

Когда я слушал лекции про дерево отрезков, дерево Фенвика, была именно такая терминология, как я описал в статье.

[@ascending]

Это совсем не повод передавать неправильную терминологию дальше.

[@basilisk]

Какой-то очевидный алгоритм с жуткими ограничениями и весьма туманной сферой применения.

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

По сути получается кеширование промежуточных значений, причём с жёсткими рамками: длина блока-«фрейма» для кеширования — sqrt(n).

Имхо, в конкретной ситуации длину блока нужно подбирать индивидуально, в зависимости от статистических характеристик входных l и r. А вдруг выяснится, что чаще всего длина блока гораздо короче sqrt(n)?

[@Flux]

Полезен только в случае, если у нас есть констатный массив и куча разных запросов на разные суммы.

В этом случае полезны частичные суммы с получением ответа за О(1), но никак не декомпозиция со сложностью O(sqrt(n)).