🗊Презентация Introduction to Segment tree

Introduction to Segment tree.

Дерево отрезков — это структура данных, которая позволяет за асимптотику 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

The Basic idea of a segment tree

Рассмотрим пример реализации дерева отрезков для следующих запросов: Рассмотрим пример реализации дерева отрезков для следующих запросов: 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]

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

Initialization of the tree void init(vector<int> &a){ size = 1; while(size <= n) size *= 2; t.resize(2 * size, 0); //0 – neutral element for “+” for (int i = 0; i < (int)a.size(); i++) t[i + size] = a[i]; for (int i = size - 1; i > 0; i--) t[i] = t[2*i]+t[2*i+1]; }

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 <= mid) change(2*v, tl, mid, i, d); else change(2*v+1, mid + 1, tr, i, d); t[v] = t[2*v] + t[2*v+1]; } change(1, 0, size - 1, i, d); //Start

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);

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”

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

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

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);

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);

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