Обсуждение:Дерево Фенвика

Обьясните

Почему дерево фенвика - это дерево? 88.147.211.196 12:02, 2 августа 2008 (UTC)

Вероятно потому, что это связный граф без циклов. ~ Aleksandrit 14:55, 2 августа 2008 (UTC)

Почему это вообще граф? 88.147.211.196 15:55, 2 августа 2008 (UTC)

Потому что это совокупность объектов со связями между ними? :-) ~ Aleksandrit 16:07, 2 августа 2008 (UTC)

И какие же там связи? 88.147.211.196 18:26, 2 августа 2008 (UTC)

Насколько мне известно, с помощью дерева фенвика можно посчитать только функцию, имеющую обратную. то есть максимумы посчитать невозможно

Функцию не имеющую обратной можно считать, но только на отрезке [1;R] 88.147.214.98 10:31, 13 августа 2008 (UTC) 88.147.214.98 10:31, 13 августа 2008 (UTC)

возможно, чувачки, и максимум, и минимум, и то же самое в 2d за log^2(n) и много ещё чего возможно ;)--Leper Messiah 18:19, 5 марта 2009 (UTC)

Нельзя в дереве Фенвика нормально работать с минимумами / максимумами 95.84.59.130 12:34, 9 апреля 2009 (UTC)

Давай на спор. Я говорю, что можно. В инете есть инфа, правда не в открытом доступе. Но если попросишь (тут или по аське 319-201) — скажу, где её можно взять, а если что, то и объясню.--Leper Messiah 19:01, 9 апреля 2009 (UTC)

Было бы интересно посмотреть 95.84.59.130 13:41, 10 апреля 2009 (UTC) 88.147.182.230 13:42, 10 апреля 2009 (UTC)

Думаю автор сего (человек с хэндлом ivan_metelsky на TopCoder) не будет против публикации здесь.

Оговорюсь, что в нашей стране дерево Фенвика для минимумов называют минимизатором, а для суммы — сумматором.

4.2. Минимизатор

Под минимизатором будем понимать структуру данных, выполняющую две операции: 

MODIFY (pos, value) - установить значение A[pos] равным min{A[pos], value}. 
FINDMIN (l, r) - найти минимальное из значений в таблице с индексами от l до r, то есть min{A[l], A[l+1], ..., A[r-1], A[r]}. 

Сюда опять же добавляется инициализация таблицы: 

INIT (N) - установить значения в таблице A[1..N], равными бесконечности. 

Минимизатор является менее гибкой структурой, чем сумматор, так как в минимизаторе мы не можем увеличить значение ячейки таблицы. При разработке минимизатора мы могли бы поступить точно так же, как при разработке сумматора (с заменой суммы на минимум). Однако проблема заключается в том, что умение выполнять операцию FINDMIN (l, r) для l = 1 не позволяет нам выполнять эту операцию для произвольного l. Поэтому нам придется немного усложнить структуру. 

Мы будем использовать три массива A[1..N], L[1..N], R[1..N]. Массив A будет содержать значения, находящиеся в таблице. Массив L будет аналогичен массиву S в сумматоре, а именно L[i] будет содержать минимальное из значений в таблице A на интервале индексов от PREV (i) + 1 до i. Элементы же массива R будут следующими: значение R[i] равно минимальному из значений в таблице A на интервале индексов от i до NEXT (i) - 1. В который уже раз мы замечаем, что написание операции INIT, работающей за O(N) тривиально. 


Operation INIT (N)
  For i:= 1 to N Do Begin
    A[i]:= INFINITY;
    L[i]:= INFINITY;
    R[i]:= INFINITY;
  End;
End;


Операцию MODIFY реализовать также несложно. Обновление значения A[pos] очевидно. Обновление значений L и R аналогично обновлению значений S в сумматоре. 


Operation MODIFY (pos, value)
  A[pos]:= min(A[pos], value);
  x:= pos;
  While x <= N Do Begin
    L[x]:= min(L[x], value);
    x:= NEXT (x);
  End;
  x:= pos;
  While x > 0 Do Begin
    R[x]:= min(R[x], value);
    x:= PREV (x);
  End;
End;


Рассуждая, как и при анализе операций сумматора, получаем, что время работы операции MODIFY составляет O(logN). 

Реализация операции FINDMIN основывается на следующей теореме, доказательство которой несложно и оставляется на упражнение. 

Теорема 4. Рассмотрим отрезок [l, r]. Пусть x0 = l. Будем вычислять xk = NEXT (xk-1) и остановимся, как только очередное xt > r. Пусть y0 = r. Будем вычислять yk = PREV (yk-1) и остановимся, как только очередное yp < l. Тогда xt-1 = yp-1. 

Упражнение 14. Доказать теорему 4. 

Теперь можно сделать следующее. Разобьем отрезок [l, r] на три части: [l, xt-1-1], [xt-1, yp-1], [yp-1+1, r]. Для нахождения минимума на первом отрезке будем использовать значения R, для нахождения минимума на третьем отрезке будем использовать значения L, второй отрезок состоит только из одного элемента, значение которого мы можем взять из таблицы A. Общий минимум на отрезке [l, r] будет равен минимуму из трех найденных минимумов. 


Operation FINDMIN (l, r)
  Res:= INFINITY;
  x:= l;
  While NEXT (x) <= r Do Begin
    Res:= min(Res, R[x]);
    x:= NEXT (x);
  End;
  Res:= min(Res, A[x]);
  x:= r;
  While PREV (x) >= l Do Begin
    Res:= min(Res, L[x]);
    x:= PREV (x);
  End;
  Return Res;
End;


Нетрудно видеть, что время работы операции FINDMIN составляет O(logN). 

Вообще, если чё по структуркам интересует, можешь ко мне как к олимпиаднику обращаться, только лучше на моё обсуждение, а то могу сюда и забыть зайти. Good luck. --Leper Messiah 19:21, 11 апреля 2009 (UTC)

Спасибо. Но: "Минимизатор является менее гибкой структурой, чем сумматор, так как в минимизаторе мы не можем увеличить значение ячейки таблицы." Вобщем-то я об этом и говорил.

88.147.214.185 18:38, 12 апреля 2009 (UTC)

А где пример?

Вот меня интересует вопрос, почему такие статьи сопровождаются какой то абракадаброй на псевдо-математическом языке, когда по логике вещей они должны сопровождаться примером на одном из современных языков программирования вроде C#, ну или в крайнем случае блок схему. 85.26.183.16 11:04, 14 февраля 2013 (UTC) Nimnul