Дерево Фенвика

[@agul]

Спасибо за статью, действительно, реализация проще дерева отрезков.

Одного не понял: почему код в картинках? Чтобы не копировали, а сами писали?

[@lisang]

Просто я тут еще не совсем разобрался, и то как вставляется код мне не понравилост (не отыскал подсветку синтаксиса), да и впрочем кода там 5 строк=)

[@awolf]

Тем не менее читать размазанный код с jpg — занятие не самое приятное.

[@lisang]

Согласен) Признаю ошибку)

[@agul]

<source lang="cpp">
//Your code goes here
</source>

[@lisang]

Спасибо, теперь буду знать.

[@Rustam]

я ее пытался осилить раз пять, но не смог. вопрос, вводящий меня в ступор: почему оно дерево?

[@lisang]

ваш вопрос логичен) ну можно сказть что эту структуру назвали деревом потому как есть некая связь между элементами массива, и в связи с этим его называют деревом.

[@Rustam]

www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

на третьей странице становится понятно, почему оно дерево =)

[@burdakovd]

Да, мне когда объясняли дерево Фенвика рисовали похожую картинку.

Без неё сложно понять, какой вид и смысл имеет функция G.

[@knstqq]

Ссылка мёртвая.
Вот доступная на текущий момент: citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8917&rep=rep1&type=pdf
A New Data Structure for Cumulative Frequency Tables
peter m. fenwick

[@SergeyBankevich]

Минимум и максимум необратимые операции и их нельзя использовать в качестве операции F.
А ещё не указан огромный плюс дерева Фенвика: всё это обобщается на многомерные массивы (то есть задачи типа вычислить сумму чисел в прямоугольнике) вообще без усилий.

[@lisang]

Про многомерность я с вами соглашусь а вот по поводу нахождения и максимума и минимуму, мне кажется что вы не правы.

[@SergeyBankevich]

Я не прав в том, что они необратимы или в том, что нельзя?
У вас написана формула S(L,R)=sum[R]-sum[L-1]. Перепишите её, пожалуйста, для максимума.

[@lisang]

Вы не правы по поводу того что нельзя. Вот тут вроде понятно описано.

[@SergeyBankevich]

Ну там немного другой алгоритм описан. Естественно, можно так модифицировать. Однако, там тоже написано, что для максимума уменьшать значения нельзя.

[@SergeyBankevich]

Кроме того, если вы увеличиваете какой-то элемент, то всё для максимума сработает. А если уменьшаете — нет. То есть если мы хотим вычислять только максимум на начальных отрезках массива и элементы только увеличиваются, то всё сработает. Если нет, то нет. Поправьте, если что.

[@danmiru]

Не хочется критиковать, поэтому попробую конкретный вопрос: а какие функции можно считать на этом дереве, кроме суммы? Что требуется для использования этой структуры для подсчета, например, синуса угла?

[@lisang]

Не совсем понятно в каком виде вы хотите считать синус?

[@danmiru]

Дерево Фенвика — это структура данных, дерево на массиве, которая обладает следующими свойствами:
• позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R]

Я не сильно математик, но — можем ли мы считать синус, а если нет, то почему?

PS. Минус в карму за вопрос, да, это, наверное, правильный подход.

[@lisang]

Хорошо вы можете сказать чему будет равен ваш синус от отрезка к примеру (1,2,3,4,1), и тогда я смогу ответить сможет ли данная структура его считать.

[@danmiru]

Ммм, а отрезок — это именно произвольный набор цифр в интервале, или все-таки есть в нем какая-нибудь логика? Из того, что на википедии написано, я понял, что это именно последовательность чисел от одного конца отрезка до другого. Т.е. если имелся ввиду отрезок от 1 до 4, то это будет 1,2,3,4.

Продолжая свои попытки приспособить эту структуру под собственные нужды, к примеру, для подсчета синуса — что насчет такого подхода:

Если отрезок это [a,b], то можно ли считать функцию sin(b-a)? Давайте разберемся с возможностью, для начала.

PS. Это математический форум? Я кого-то оскорбляю? Я не пытаюсь вести конструктивный диалог, в меру своих сил? Минусовать комментарии и карму — хамство.

[@SergeyBankevich]

t[i]=a[G[i]]+…+a[i]

[@SergeyBankevich]

Извиняюсь, ентер сработал не там.

В формуле t[i]=a[G[i]]+…+a[i], возможно, стоит добавить хотя бы член a[G[i] + 1], а то не совсем очевидно, что многоточие означает.

В анализе сложности вычисления суммы не совсем верно написано. Функция G, конечно, уменьшает количество единиц. Однако потом отнимается единица и количество единиц опять увеличивается. Так что либо количество единиц в G[x] — 1 больше, чем у x и мы заканчиваем, когда G[x] — 1 = -1, либо количество нулей у G[x — 1] больше, чем у x.

[@tvolf]

Так всё-таки, какова формула для заполнения массива частичных сумм t? Что должно быть вместо многоточия? А то действительно не очень понятно.

[@lisang]

Я же вроде бы добавил еще один элемент к последовательности.
t[i]=a[G[i]]+a[G[i]+1]…+a[i] (сумма всех элементов начиная a[G[i]] и до a[i])/

[@karlicos]

Вообще не очень понятно, что именно имеется в виду под обратимой операцией. По идее, операцией op может быть любая, для которой:
op(a, b) = op(op(a, c), op(c + 1, b)). То есть, если мы знаем результаты операций для подотрезков, мы однозначно считаем результат для отрезка. Сумма под это подходит, максимум — минимум подходят, к примеру. Можно хоть произведение считать.
А чтобы посчитать сумму в прямоугольнике(2мерный случай), например, надо использовать принцип включения-исключения.

[@karlicos]

да, такие операции ассоциативными называются

[@SergeyBankevich]

Обратимость операции означает, что найдётся такая операция F', что a = F'(F(a, b), b). То есть для сложения это вычитание. Для умножения это деление. А вот для максимума и минимума операция F' есть не для всех значений a и b. Например, если я знаю max(a, b) и знаю b, то a всё равно не смогу вычислить, если b = max(a, b).
Поэтому, во-первых, алгоритм надо менять, чтобы не использовать фомулу S(L,R)=sum[R]-sum[L-1]: для максимума её нет. А во-вторых, нельзя уменьшать значения, потому что пересчитать массив t мы в таком случае не сможем.

[@burdakovd]

Можно было ещё указать преимущества и недостатки в сравнении с деревом отрезков:

Преимущества:
— уже упомянутая простота и скорость
— памяти занимает не просто O(N), а даже ровно N, то есть нет дополнительных затрат памяти

Недостатки:
— функция должна быть обратимой, а это значит, что минимум и максимум это дерево считать не может (исправьте определение функции F)

Ну и чтобы не дублировать код, можно было представить sum(L, R) в виде разности sum® — sum(L-1) (почти)

[@burdakovd]

sum( R ) // хабрапарсер жжет

[@burdakovd]

Сумма обратима, т.к. зная s+x и x можно вычислить s = (s+x) — x
Максимум/минимум не обратим, т.к. зная max(s, x) и x нельзя вычислить s (в общем случае)

Примеры обратимых функции: *, xor
Необратимых: &, |, min, max

[@lisang]

Сейчас подправлю.

[@Skiminok]

У вас сложный код, как суммы, так и модификации :)
Это же все то же самое можно в несколько строчек записать, если чуть видоизменить операцию перехода. Тогда она, тем более, становится одинаковой для обоих циклов — запоминать проще.

Сумма на отрезке [1; X]:

int sum(int X) {
    int ans = 0;
    for (int i = X; i > 0; i -= i & -i)
        ans += t[i];
    return ans;
}

Обновление в точке A[X] += V:

void update(int X, int V) {
    for (int i = X; i <= N; i += i & -i)
        t[i] += V;
}

[@lisang]

Посути ничего нового вы не написали, но за другой вариант спасибо.

[@burdakovd]

А я сколько пытался запомнить — каждый раз заново вывожу формулу перехода.

Тем более она бывает разной в зависимости от того, как индексировать отрезок: с 0 или с 1.

[@metar]

Есть классная статья про деревья Фенвика с картинками (sic!) на топкодере, правда, на английском.

[@iasonov]

В рамках небольшого восстановления исторической справедливости - впервые эта структура была описана нашим соотечественником Борисом Рябко в 1989 году.