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

Июль 29, 2022

Главная
Информатика
Дерево Фенвика

Содержание

2. Немного истории Впервые эта структура была описана Рябко Б.Я. в 1989 году. Полная версия опубликована им
3. Что это? Что умеет? О_о Дерево Фенвика – это структура данных, дерево на массиве, обладающее следующими
4. Решим задачку! Дан массив a длины N. Поступают запросы: найти сумму на отрезке [L, R] прибавить
5. А зачем тут дерево Фенвика? Такую задачу мы уже умеем решать используя дерево отрезков или sqrt-декомпозицию.
6. Ну и как оно работает? В дереве Фенвика t[i] отвечает за сумму на отрезке длины len,
7. Пояснительная бригада картиночка Пояснительный пример. Рассмотрим t[12]. Максимальная степень двойки, на которую делится 12 – это
8. Внимание, вопрос! А как узнать эту самую максимальную степень двойки? Тут несколько вариантов. Ее можно просто
9. (Не)много логики
10. Ничего непонятно, хочу пример
11. ✨Сейчас будет магия✨ Внезапно поговорим об отрицательных числах! Как они выглядят вообще в двоичной записи? Так
12. Пример
13. А дальше?
14. А как так вышло? Разберем все по порядку. Как мы получали отрицательное число? Сначала меняли все
15. Нууу… Вроде понятно, но так… в общих чертах Таким образом, t[i] – отвечает за отрезок длины
16. А как искать на моем отрезке? Дерево Фенвика умеет искать сумму на префиксе. Тогда сумма на
17. Хачу код GetSum То есть на каждом шаге мы добавляем в ответ сумму на отрезке, за
18. А изменение элемента??? То есть на каждом шаге мы добавляем x в t[i], а дальше переходим
19. А почему?...
20. А всегда ли так? Если простыми словами, как выглядит нашл переход. В числе i в конце
21. Примерчик Как видим, длина действительно увеличится минимум в 2 раза. Теперь докажем, что каждый следующий отрезок
22. Очевидно. Доказательство.
23. А почему быстро работает? Рассмотрим функцию GetSum. Как у нас изменяется i на каждом шаге? Если
24. А может Update долго работает?
25. Выводы Дерево Фенвика работает быстро, занимает мало памяти, пишется быстрее. Также его можно применять в двумерном
26. Что почитать? ru.algorithmica.org/cs/range-queries/fenwick/ e-maxx.ru/algo/fenwick_tree neerc.ifmo.ru/wiki/index.php?title=Дерево_Фенвика
28. Скачать презентацию

Слайд 2

Немного истории
Впервые эта структура была описана Рябко Б.Я. в 1989 году.

Полная версия опубликована им на английском в 1992 г.
Через два года (в 1994 г.) появилась статья П. Фенвика, где была описана та же структура, впоследствии получившая название "дерево Фенвика".

Слайд 3

Что это? Что умеет? О_о
Дерево Фенвика – это структура данных, дерево

на массиве, обладающее следующими свойствами:
позволяет вычислять значение некоторой обратимой операции на любом отрезке [L, R] за время O (log N)
изменение элемента за O(log N)
требует O(N) памяти
легко обобщается на случай многомерных массивов.

Слайд 4

Решим задачку!
Дан массив a длины N.
Поступают запросы:
найти сумму на

отрезке [L, R]
прибавить элементу на позиции p значение x

Слайд 5

А зачем тут дерево Фенвика?
Такую задачу мы уже умеем решать используя

дерево отрезков или sqrt-декомпозицию. Но дерево отрезков требует O(4N) памяти, а sqrt-декомпозиция в худшем случае будет работать слишком долго.
Вывод: используем дерево Фенвика.

Слайд 6

Ну и как оно работает?
В дереве Фенвика t[i] отвечает за сумму

на отрезке длины len, который заканчивается в элементе i.
len – максимальная степень двойки, на которую делится число i.

Слайд 7

Пояснительная бригада картиночка
Пояснительный пример.
Рассмотрим t[12]. Максимальная степень двойки, на которую делится

12 – это 4. Значит в t[12] хранится ответ для отрезка [9, 12].
Аналогично для всех t[i].

Слайд 8

Внимание, вопрос!
А как узнать эту самую максимальную степень двойки?
Тут несколько

вариантов. Ее можно просто подсчитать и записать в отдельный массив. Но есть вариант и без дополнительной памяти.

Слайд 9

(Не)много логики

Слайд 10

Ничего непонятно, хочу пример

Слайд 11

✨Сейчас будет магия✨
Внезапно поговорим об отрицательных числах!
Как они выглядят вообще в

двоичной записи? Так вот, чтобы получить отрицательное число, в его двоичной записи меняют все единички на нолики, а нолики на единички. А потом прибавляем к нему 1.

Слайд 12

Пример

Слайд 13

А дальше?

Слайд 14

А как так вышло?
Разберем все по порядку. Как мы получали отрицательное

число? Сначала меняли все 1 на 0, а 0 на 1. То есть на этом шаге у нас не совпадают значения ни в одном бите. Также можно заметить, что все нули в конце стали единицами. Что произойдет, если добавить 1? Все единицы в конце станут 0, а самый правый 0 станет 1. Остальные значения не изменятся, а значит после побитового AND единица будет только в 1 месте – в позиции самой правой единицы.

Слайд 15

Нууу… Вроде понятно, но так… в общих чертах
Таким образом, t[i] –

отвечает за отрезок длины len = i AND (-i).
Теперь мы умеем считать длину отрезка, и немного понимаем откуда такая формула. Вернемся к нашей задачке!

Слайд 16

А как искать на моем отрезке?
Дерево Фенвика умеет искать сумму на

префиксе. Тогда сумма на отрезке с границами L и R равна:
GetSum(R) – GetSum(L – 1)

Слайд 17

Хачу код GetSum
То есть на каждом шаге мы добавляем в ответ

сумму на отрезке, за который отвечает i-тый элемент, а потом полностью перескакиваем этот отрезок и переходим к следующему.

Слайд 18

А изменение элемента???
То есть на каждом шаге мы добавляем x в

t[i], а дальше переходим в следующий отрезок. Этот отрезок тоже будет включать в себя позицию pos, но его длина будет больше.

Слайд 19

А почему?...

Слайд 20

А всегда ли так?
Если простыми словами, как выглядит нашл переход.
В числе

i в конце стоит какое-то количество нулей (возможно 0). Мы берем самую правую 1, меняем ее на ноль, и идем по числу влево, пока не встретим ноль. На этом пути мы меняем все 1 на 0, а на место найденного нами нуля ставим 1. А значит, мы увеличим минимум на 1 количество нулей в конце числа, а значит длину отрезка – минимум в 2 раза.

Слайд 21

Примерчик

Как видим, длина действительно увеличится минимум в 2 раза.
Теперь докажем,

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

Слайд 22

Очевидно. Доказательство.

Слайд 23

А почему быстро работает?
Рассмотрим функцию GetSum. Как у нас изменяется i

на каждом шаге? Если говорить простыми словами, то мы находим самую правую единицу и вместо нее ставим 0. И делаем это пока i ≠ 0. То есть сумма ищется за количество 1 в числе, а значит в худшем случае поиск суммы займет O(log N) времени.

Слайд 24

А может Update долго работает?

Слайд 25

Выводы
Дерево Фенвика работает быстро, занимает мало памяти, пишется быстрее. Также его

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

Слайд 26