Комментарии 39
Спасибо за статью, действительно, реализация проще дерева отрезков.
Одного не понял: почему код в картинках? Чтобы не копировали, а сами писали?
Одного не понял: почему код в картинках? Чтобы не копировали, а сами писали?
Просто я тут еще не совсем разобрался, и то как вставляется код мне не понравилост (не отыскал подсветку синтаксиса), да и впрочем кода там 5 строк=)
я ее пытался осилить раз пять, но не смог. вопрос, вводящий меня в ступор: почему оно дерево?
ваш вопрос логичен) ну можно сказть что эту структуру назвали деревом потому как есть некая связь между элементами массива, и в связи с этим его называют деревом.
www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf
на третьей странице становится понятно, почему оно дерево =)
на третьей странице становится понятно, почему оно дерево =)
Да, мне когда объясняли дерево Фенвика рисовали похожую картинку.
Без неё сложно понять, какой вид и смысл имеет функция G.
Без неё сложно понять, какой вид и смысл имеет функция G.
Ссылка мёртвая.
Вот доступная на текущий момент: 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
Вот доступная на текущий момент: 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
Минимум и максимум необратимые операции и их нельзя использовать в качестве операции F.
А ещё не указан огромный плюс дерева Фенвика: всё это обобщается на многомерные массивы (то есть задачи типа вычислить сумму чисел в прямоугольнике) вообще без усилий.
А ещё не указан огромный плюс дерева Фенвика: всё это обобщается на многомерные массивы (то есть задачи типа вычислить сумму чисел в прямоугольнике) вообще без усилий.
Про многомерность я с вами соглашусь а вот по поводу нахождения и максимума и минимуму, мне кажется что вы не правы.
Я не прав в том, что они необратимы или в том, что нельзя?
У вас написана формула S(L,R)=sum[R]-sum[L-1]. Перепишите её, пожалуйста, для максимума.
У вас написана формула S(L,R)=sum[R]-sum[L-1]. Перепишите её, пожалуйста, для максимума.
Вы не правы по поводу того что нельзя. Вот тут вроде понятно описано.
Кроме того, если вы увеличиваете какой-то элемент, то всё для максимума сработает. А если уменьшаете — нет. То есть если мы хотим вычислять только максимум на начальных отрезках массива и элементы только увеличиваются, то всё сработает. Если нет, то нет. Поправьте, если что.
Не хочется критиковать, поэтому попробую конкретный вопрос: а какие функции можно считать на этом дереве, кроме суммы? Что требуется для использования этой структуры для подсчета, например, синуса угла?
Не совсем понятно в каком виде вы хотите считать синус?
Дерево Фенвика — это структура данных, дерево на массиве, которая обладает следующими свойствами:
• позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R]
Я не сильно математик, но — можем ли мы считать синус, а если нет, то почему?
PS. Минус в карму за вопрос, да, это, наверное, правильный подход.
• позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R]
Я не сильно математик, но — можем ли мы считать синус, а если нет, то почему?
PS. Минус в карму за вопрос, да, это, наверное, правильный подход.
Хорошо вы можете сказать чему будет равен ваш синус от отрезка к примеру (1,2,3,4,1), и тогда я смогу ответить сможет ли данная структура его считать.
Ммм, а отрезок — это именно произвольный набор цифр в интервале, или все-таки есть в нем какая-нибудь логика? Из того, что на википедии написано, я понял, что это именно последовательность чисел от одного конца отрезка до другого. Т.е. если имелся ввиду отрезок от 1 до 4, то это будет 1,2,3,4.
Продолжая свои попытки приспособить эту структуру под собственные нужды, к примеру, для подсчета синуса — что насчет такого подхода:
Если отрезок это [a,b], то можно ли считать функцию sin(b-a)? Давайте разберемся с возможностью, для начала.
PS. Это математический форум? Я кого-то оскорбляю? Я не пытаюсь вести конструктивный диалог, в меру своих сил? Минусовать комментарии и карму — хамство.
Продолжая свои попытки приспособить эту структуру под собственные нужды, к примеру, для подсчета синуса — что насчет такого подхода:
Если отрезок это [a,b], то можно ли считать функцию sin(b-a)? Давайте разберемся с возможностью, для начала.
PS. Это математический форум? Я кого-то оскорбляю? Я не пытаюсь вести конструктивный диалог, в меру своих сил? Минусовать комментарии и карму — хамство.
t[i]=a[G[i]]+…+a[i]
Извиняюсь, ентер сработал не там.
В формуле t[i]=a[G[i]]+…+a[i], возможно, стоит добавить хотя бы член a[G[i] + 1], а то не совсем очевидно, что многоточие означает.
В анализе сложности вычисления суммы не совсем верно написано. Функция G, конечно, уменьшает количество единиц. Однако потом отнимается единица и количество единиц опять увеличивается. Так что либо количество единиц в G[x] — 1 больше, чем у x и мы заканчиваем, когда G[x] — 1 = -1, либо количество нулей у G[x — 1] больше, чем у x.
В формуле t[i]=a[G[i]]+…+a[i], возможно, стоит добавить хотя бы член a[G[i] + 1], а то не совсем очевидно, что многоточие означает.
В анализе сложности вычисления суммы не совсем верно написано. Функция G, конечно, уменьшает количество единиц. Однако потом отнимается единица и количество единиц опять увеличивается. Так что либо количество единиц в G[x] — 1 больше, чем у x и мы заканчиваем, когда G[x] — 1 = -1, либо количество нулей у G[x — 1] больше, чем у x.
Вообще не очень понятно, что именно имеется в виду под обратимой операцией. По идее, операцией op может быть любая, для которой:
op(a, b) = op(op(a, c), op(c + 1, b)). То есть, если мы знаем результаты операций для подотрезков, мы однозначно считаем результат для отрезка. Сумма под это подходит, максимум — минимум подходят, к примеру. Можно хоть произведение считать.
А чтобы посчитать сумму в прямоугольнике(2мерный случай), например, надо использовать принцип включения-исключения.
op(a, b) = op(op(a, c), op(c + 1, b)). То есть, если мы знаем результаты операций для подотрезков, мы однозначно считаем результат для отрезка. Сумма под это подходит, максимум — минимум подходят, к примеру. Можно хоть произведение считать.
А чтобы посчитать сумму в прямоугольнике(2мерный случай), например, надо использовать принцип включения-исключения.
да, такие операции ассоциативными называются
Обратимость операции означает, что найдётся такая операция 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 мы в таком случае не сможем.
Поэтому, во-первых, алгоритм надо менять, чтобы не использовать фомулу S(L,R)=sum[R]-sum[L-1]: для максимума её нет. А во-вторых, нельзя уменьшать значения, потому что пересчитать массив t мы в таком случае не сможем.
Можно было ещё указать преимущества и недостатки в сравнении с деревом отрезков:
Преимущества:
— уже упомянутая простота и скорость
— памяти занимает не просто O(N), а даже ровно N, то есть нет дополнительных затрат памяти
Недостатки:
— функция должна быть обратимой, а это значит, что минимум и максимум это дерево считать не может (исправьте определение функции F)
Ну и чтобы не дублировать код, можно было представить sum(L, R) в виде разности sum® — sum(L-1) (почти)
Преимущества:
— уже упомянутая простота и скорость
— памяти занимает не просто O(N), а даже ровно N, то есть нет дополнительных затрат памяти
Недостатки:
— функция должна быть обратимой, а это значит, что минимум и максимум это дерево считать не может (исправьте определение функции F)
Ну и чтобы не дублировать код, можно было представить sum(L, R) в виде разности sum® — sum(L-1) (почти)
У вас сложный код, как суммы, так и модификации :)
Это же все то же самое можно в несколько строчек записать, если чуть видоизменить операцию перехода. Тогда она, тем более, становится одинаковой для обоих циклов — запоминать проще.
Сумма на отрезке
Обновление в точке
Это же все то же самое можно в несколько строчек записать, если чуть видоизменить операцию перехода. Тогда она, тем более, становится одинаковой для обоих циклов — запоминать проще.
Сумма на отрезке
[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;
}
НЛО прилетело и опубликовало эту надпись здесь
Есть классная статья про деревья Фенвика с картинками (sic!) на топкодере, правда, на английском.
В рамках небольшого восстановления исторической справедливости - впервые эта структура была описана нашим соотечественником Борисом Рябко в 1989 году.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Дерево Фенвика