Introduction to Fenwick tree - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Introduction to Fenwick tree. Доклад-сообщение содержит 15 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Дерево Фенвика Introduction to Fenwick tree

Слайд 2

Описание слайда:

Дерево Фе́нвика — структура данных, требующая O(n) памяти и позволяющая эффективно (за O(log n)) выполнять следующие операции: Дерево Фе́нвика — структура данных, требующая O(n) памяти и позволяющая эффективно (за O(log n)) выполнять следующие операции: Memory: O(n) , Time: O(log n) Operations изменять значение любого элемента в массиве, To change the value of any element in the array выполнять некоторую ассоциативную, коммутативную, и обратимую операцию на отрезке. To calculate some associative and commutative functions on the interval

Слайд 3

Описание слайда:

There is an array A[0..N-1]. There is an array A[0..N-1]. Let’s construct an array Т[0..N-1] where is some function, we will discuss it below.

Слайд 4

Описание слайда:

Теперь мы можем реализовать следующие функции: Теперь мы можем реализовать следующие функции:

Слайд 5

Описание слайда:

Что за функция F - ? Let , where «&» is bitwise AND.

Слайд 6

Описание слайда:

Что за функция F - ? Let , where «&» is bitwise AND. How can we find for given i all the j that F(j) <= i <= j

Слайд 7

Описание слайда:

Что за функция F - ? Let , where «&» is bitwise AND. How can we find for given i all the j that F(j) <= i <= j Let’s use , where «|» is bitwise OR.

Слайд 8

Описание слайда:

Слайд 9

Описание слайда:

Initialization in O(N log N)

Слайд 10

Описание слайда:

Initialization in O(N)

Слайд 11

Описание слайда:

Advantages It allows to calculate the value of some associative, commutative operations on the interval [L; R] and to change the value of any element in O (log N) Memory in O(N) The easy implementation It can be easy transformed into 2D and 3D arrays

Слайд 12

Описание слайда:

2D Fenwick Tree

Слайд 13

Описание слайда:

Disadvantages The using operation in Fenwick Tree must be reversible, so it can’t work with “maximum” and “minimum” operations well on intervals.

Слайд 14

Описание слайда:

…but! При некоторой модификации, мы всё же сможем работать с минимумом (с максимумом) на отрезке, но с ограничениями. Так же дерево можно модифицировать для изменения элементов на отрезке. We can modify it so it can work even with max and min (with some limitation). The tree can be modified to work with changing elements on the interval.