Обсуждение:Статистики на отрезках. Корневая эвристика

2012-05-25T07:21:38Z

109.188.163.226:

: {{tick | ticked=1}} категории
: {{tick | ticked=1}} мелочь, но все же когда пишут for i = a to b, это — по закрытому интервалу, так что лучше for i = 0 to n-1.
: {{tick | ticked=1}} лучше один раз напиши вначале, что у тебя это все строится над ассоциативной операцией (да по идее, это даже уже есть в опеределении), а дальше не перечисляй постоянно сумма/максимум/минимум. Просто говори «операция».
: {{tick | ticked=1}} нормально расписать среди каких элементов надо искать минимум, а то там какие-то левые k.
: {{tick | ticked=1}} Оценку лучше для каждой операции написать отдельно, потому что, например, по не совсем удачному примеру изменения создается ощущение, что его за O(1) можно делать.
: {{tick}} Собственно, про изменение — поменять-то надо два элемента, но это не означает O(1). При подсчете суммы просто повезло, что изменение элемента совпадает с изменением всего блока. Был бы минимум или произведение — пришлось бы заново пересчитывать всю операцию в блоке, так что лучше напиши псевдокод минимума/максимума/произведения.
:: «то нам необходимо поменять всего два элемента» — два элемента поменяются в обоих случаях же, просто количество операций будет разное.
::: {{tick}} Опять про два элемента. Да их в любом случае два изменится.
:::: Опять кривая формулировка. Значение для блока мы итак пересчитываем в обеих случаях. Просто прямо там же напиши, что в первом случае мы можем за O(1), а во втором — за O(sqrt(n)).
:: {{tick|ticked=1}} А ты уверен, что запрос на изменение должен принимать delta? Было бы странно, так как у тебя всегда происходит прибавление, а мы как-то пытаемся абстрагироваться. Мне кажется, просто нужна замена одного элемента другим.
:: {{tick|ticked=1}}Ты, видимо, хотел сказать, что если есть обратная операция, можно за O(1) делать изменение? Мне кажется, это неверно, нужна еще коммутативность. Например, с умножением и ненулевыми числами, это вроде работает:
change(i, newValue):
other = B[i / len] * inverse(A[i]) // типа деление
A[i] = newValue
B[i / len] = other * newValue
:: С произведением матриц такая штука уже, видимо, не прокатит. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 10:29, 16 мая 2012 (GST)

: {{tick | ticked=1}} чтобы указать границы операции min, использовать \limits\
: {{tick | ticked=1}} Ну и вообще поправить всякий треш, а то тут сплошная копипаста емакса. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 23:50, 6 февраля 2012 (MSK)
: {{tick}} изменение:
:: {{tick|ticked=1}} в псевдокоде одном случае используется абстрактная операция <tex> \circ </tex>, а в другом — минимум. Используй и там и там абстрактную лучше.
:: {{tick|ticked=1}}Код для минимума вообще неправильный, у тебя в блоке будет всегда минимум двух его последних элементов.
:: {{tick|ticked=1}}почему в одном случае изменяется элемент i, а во втором — p? Пусть переменные будут одинаковые, и вообще, почитай правила оформления псевдокода и оформи весь код как функции, которые принимают индекс того, что изменить и новое значение, например (это и к остальному коду относится).
:: {{tick|ticked=1}} Напиши, что фича первой реализации в том, что она за O(1) может происходить, а вторая — за O(sqrt(n)).
:: {{tick|ticked=1}} index = len * (p / cnt) — мне кажется, ты хотел сказать index = len * (p / len), не?
:: {{tick}} «B[p / len] = A[index]; for i = index + 1 to index + len - 1; B[p / len] = B[p / len] o A[i]» — Лучше присвоить значение блока сначала нейтральному элементу, а потом нормально пробегаться по всем элементам блока. Также это к precalc относится. И к запросу.
:: {{tick}} Кстати, в таких случаях «запрос» принято переаводить не как request, а как query, и change как set. И precalc я бы переименовал в build (соответственно, «предподсчет» в «построение», у нас все-таки какая-никакая — а структура данных).

Обсуждение:Многомерное дерево отрезков

2012-05-25T06:58:39Z

109.188.163.226:

: {{tick|ticked=1}} Проставить категории, нормально оформить источники.
: {{tick}} Использовать абстрактную ассоциативную операцию, а не только сумму/максимум.
:: Я все же настаиваю на том, что нужна абстрактная операция, с ней будет большее понимание, что вообще происходит, больше внимания будет обращено на детали, связанные со структурой дерева, а не с особенностями конкретное операции.
: {{tick|ticked=1}} В пункте «Хранение» какая-то хрень.
: {{tick}} написать псевдокод
::: псевдокод чуть менее чем полностью идентичен емаксу. С точностью до бессмысленных имен переменных (tlx, trx и т.д.).
: {{tick}} написать более подробное объяснение.
:: Объяснения все еще по сути нет, только код. Нужно описание и к запросу и к обновлению.
: {{tick}} Рассматривать только двумерный случай - уг. Как раз таки, это не облегчает понимание. Нужно подробное описание n-мерного случая и псевдокод.
--[[Участник:Dgerasimov|Дмитрий Герасимов]] 18:46, 24 мая 2012 (GST)

Викиконспекты - Вклад участника [ru]

Обсуждение:Статистики на отрезках. Корневая эвристика

Обсуждение:Многомерное дерево отрезков