1679
правок
Изменения
Нет описания правки
: {{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). При подсчете суммы просто повезло, что изменение элемента совпадает с изменением всего блока. Был бы минимум или произведение — пришлось бы заново пересчитывать всю операцию в блоке, так что лучше напиши псевдокод минимума/максимума/произведения.
:: «то нам необходимо поменять всего два элемента» — два элемента поменяются в обоих случаях же, просто количество операций будет разное.
:: А ты уверен, что запрос на изменение должен принимать delta? Было бы странно, так как у тебя всегда происходит прибавление, а мы как-то пытаемся абстрагироваться. Мне кажется, просто нужна замена одного элемента другим.
:: Ты, видимо, хотел сказать, что если есть обратная операция, можно за 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)
