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

☑ категории

☑ мелочь, но все же когда пишут for i = a to b, это — по закрытому интервалу, так что лучше for i = 0 to n-1.

☑ лучше один раз напиши вначале, что у тебя это все строится над ассоциативной операцией (да по идее, это даже уже есть в опеределении), а дальше не перечисляй постоянно сумма/максимум/минимум. Просто говори «операция».

☑ нормально расписать среди каких элементов надо искать минимум, а то там какие-то левые k.

☑ Оценку лучше для каждой операции написать отдельно, потому что, например, по не совсем удачному примеру изменения создается ощущение, что его за O(1) можно делать.

☐ Собственно, про изменение — поменять-то надо два элемента, но это не означает O(1). При подсчете суммы просто повезло, что изменение элемента совпадает с изменением всего блока. Был бы минимум или произведение — пришлось бы заново пересчитывать всю операцию в блоке, так что лучше напиши псевдокод минимума/максимума/произведения.

«то нам необходимо поменять всего два элемента» — два элемента поменяются в обоих случаях же, просто количество операций будет разное.

А ты уверен, что запрос на изменение должен принимать delta? Было бы странно, так как у тебя всегда происходит прибавление, а мы как-то пытаемся абстрагироваться. Мне кажется, просто нужна замена одного элемента другим.

Ты, видимо, хотел сказать, что если есть обратная операция, можно за O(1) делать изменение? Мне кажется, это неверно, нужна еще коммутативность. Например, с умножением и ненулевыми числами, это вроде работает:

change(i, newValue):
    other = B[i / len] * inverse(A[i]) // типа деление
    A[i] = newValue
    B[i / len] = other * newValue

С произведением матриц такая штука уже, видимо, не прокатит. --Дмитрий Герасимов 10:29, 16 мая 2012 (GST)

☑ чтобы указать границы операции min, использовать \limits\

☑ Ну и вообще поправить всякий треш, а то тут сплошная копипаста емакса. --Дмитрий Герасимов 23:50, 6 февраля 2012 (MSK)