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

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

Содержание ▲

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

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

Слайд 1

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

Introduction to Segment tree.

Слайд 2

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

Дерево отрезков — это структура данных, которая позволяет за асимптотику O(log n) реализовать любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции. Дерево отрезков — это структура данных, которая позволяет за асимптотику O(log n) реализовать любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции. Но стоит заметить, что класс задач, решаемых с помощью дерева отрезков, намного больше. Segment tree – is a data structure that allows to implement operations on the interval in O(log n). The operation should have an associative property and have a neutral element

Слайд 3

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

The Basic idea of a segment tree

Слайд 4

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

Рассмотрим пример реализации дерева отрезков для следующих запросов: Рассмотрим пример реализации дерева отрезков для следующих запросов: 1) Добавить к i-му элементу значение d 2) Получить сумму на отрезке [l;r] The Example of queries for the segment tree: To add a value d to the value of i-th element To get sum on the segment [l;r]

Слайд 5

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

Creating structure struct Tree { vector t; int size; };

Слайд 6

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

Initialization of the tree void init(vector &a){ size = 1; while(size 0; i--) t[i] = t[2*i]+t[2*i+1]; }

Слайд 7

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

The change request void change(int v, int tl, int tr, int i, int d){ if (tl == tr){ t[v] += d; return; } int mid = (tl + tr) / 2; if (i

Слайд 8

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

Getting sum int sum(int v, int tl, int tr, int l, int r){ if (l > r) return 0; if (tl == l && tr == r){ return t[v]; } int mid = (tl + tr) / 2; int left_sum = sum(2*v, tl, mid, l, min(r, mid)); int right_sum = sum(2*v+1, mid+1, tr, max(l, mid+1), r); return left_sum + right_sum; } sum(1, 0, size - 1, l, r);

Слайд 9

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

Let’s make the task more difficult Запросы: 1) Изменить значение элементов [l;r] на d 2) Получить сумму на [l;r] Для этого нам придётся воспользоваться методом «запаздывающего обновления». Requests: 1) Add the value d to every element on the segment [l;r] 2) Get sum on the segment [l;r] We use the method of “lazy propagation”

Слайд 10

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

struct Tree struct Tree { vector t; vector add // array for method of “lazy propagation” int size; void init(vector &a, int n){ size = 1; while(size 0; i--) t[i] = t[2*i]+t[2*i+1]; } };

Слайд 11

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

The main function of the method void push(int v){ add[2*v]+= add[v]; add[2*v+1]+= add[v]; add[v] = 0; }

Слайд 12

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

The change request void change(int v, int tl, int tr, int l, int r, int d){ if (l > r) return; if (tl == l && tr == r){ add[v] += d; return; } push(v); int mid = (tl + tr) / 2; change(2*v, tl, mid, l, min(r, mid), d); change(2*v+1, mid + 1, tr, max(l, mid + 1), r, d); t[v] = t[2*v] + (mid - tl + 1) * add[2*v] + t[2*v+1] + (r - mid) * add[2*v+1]; } change(1, 0, size - 1, l, r, d);

Слайд 13

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

Getting sum int sum(int v, int tl, int tr, int l, int r){ if (l > r) return 0; if (tl == l && tr == r){ return t[v] + add[v] * (r - l + 1);; } push(v); int mid = (tl + tr) / 2; int left_sum = sum(2*v, tl, mid, l, min(r, mid)); int right_sum = sum(2*v+1, mid+1, tr, max(l, mid+1), r); t[v] = t[2*v] + (mid - tl + 1) * add[2*v] + t[2*v+1] + (r - mid) * add[2*v+1]; return left_sum + right_sum; } sum(1, 0, size - 1, l, r);

Слайд 14

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

Useful links neerc.ifmo.ru: Дерево отрезков. Построение Реализация запроса в дереве отрезков сверху Несогласованные поддеревья. Реализация массового обновления E-maxx. Дерево отрезков – описано большое количество задач, которые решаются деревом отрезков с решением. Codeforces (Eng article)