Comments 12
Не хочется сходу обвинять автора в отсутствии фантазии, но чем данная статья отличается от, например, этой?
Для, именно вами указанной, постановки задачи оптимальным будет алгоритм, когда мы в D[i] заносим сумму длин отрезков с 0 по i. И ответ считаем как D[r]-D[l-1].
Ваше решение имеет право на жизнь, если изменение элементов массива происходит довольно часто, но не чаще чем «корень из n» изменений на одно считывание. Иначе полный пересчет опять становится эффективнее.
Ваше решение имеет право на жизнь, если изменение элементов массива происходит довольно часто, но не чаще чем «корень из n» изменений на одно считывание. Иначе полный пересчет опять становится эффективнее.
По идее, это работает для любой ассоциативной операции — минимума, например.
еще оно хорошо тем, что легко можно добавить еще одну операцию — изменение на отрезке, например.
Ваш метод с D[i] выигрывает, если изменение элементов массива A происходит редко, потому что при каждом изменении элемента j приходится пересчитывать все D[i], у которых i >= j. А «авторский» метод более универсален.
Короче говоря, постановки задачи — расплывчатая, т.к. сильно зависит от частоты изменения/удаления элементов массива. Если например, элементы массива изменяются в 1000 раз чаще, чем считается эта пресловутая сумма от l до r, то выгоднее вообще не содержать никакого массива B, а тупо суммировать простым циклом от l до r.
Короче говоря, постановки задачи — расплывчатая, т.к. сильно зависит от частоты изменения/удаления элементов массива. Если например, элементы массива изменяются в 1000 раз чаще, чем считается эта пресловутая сумма от l до r, то выгоднее вообще не содержать никакого массива B, а тупо суммировать простым циклом от l до r.
Одному мне мерещится массив из 1 000 000 элементов и постоянные запросы на частичную сумму из 999 слагаемых?
Второе предложение в статье:
> «… это древо отрезков(RSQ), но он довольно сложен в написании и понимании»
Оба утверждения не верны.
RSQ — это Range Sum Query. Это вовсе не дерево отрезков, а задача, которую Вы решаете (запросы о сумме на отрезке).
И сложного ничего нет ни в написании, ни в понимании дерева отрезков.
Как раз сегодня (ирония detected!) мой коллега рассказал школьникам на кружке (8—10 класс) дерево отрезков за одно занятие без проблем.
> «… это древо отрезков(RSQ), но он довольно сложен в написании и понимании»
Оба утверждения не верны.
RSQ — это Range Sum Query. Это вовсе не дерево отрезков, а задача, которую Вы решаете (запросы о сумме на отрезке).
И сложного ничего нет ни в написании, ни в понимании дерева отрезков.
Как раз сегодня (ирония detected!) мой коллега рассказал школьникам на кружке (8—10 класс) дерево отрезков за одно занятие без проблем.
Какой-то очевидный алгоритм с жуткими ограничениями и весьма туманной сферой применения.
Полезен только в случае, если у нас есть констатный массив и куча разных запросов на разные суммы. Практическую задачу для этого я придумать сходу не могу (но не отрицаю, что она есть).
По сути получается кеширование промежуточных значений, причём с жёсткими рамками: длина блока-«фрейма» для кеширования — sqrt(n).
Имхо, в конкретной ситуации длину блока нужно подбирать индивидуально, в зависимости от статистических характеристик входных l и r. А вдруг выяснится, что чаще всего длина блока гораздо короче sqrt(n)?
Полезен только в случае, если у нас есть констатный массив и куча разных запросов на разные суммы. Практическую задачу для этого я придумать сходу не могу (но не отрицаю, что она есть).
По сути получается кеширование промежуточных значений, причём с жёсткими рамками: длина блока-«фрейма» для кеширования — sqrt(n).
Имхо, в конкретной ситуации длину блока нужно подбирать индивидуально, в зависимости от статистических характеристик входных l и r. А вдруг выяснится, что чаще всего длина блока гораздо короче sqrt(n)?
Sign up to leave a comment.
Sqrt-декомпозиция