Introduction to Segment tree

Июль 29, 2022

Главная
Информатика
Introduction to Segment tree

Содержание

3. The Basic idea of a segment tree
4. Рассмотрим пример реализации дерева отрезков для следующих запросов: 1) Добавить к i-му элементу значение d 2)
5. Creating structure struct Tree { vector t; int size; };
6. Initialization of the tree void init(vector &a){ size = 1; while(size t.resize(2 * size, 0); //0
7. The change request void change(int v, int tl, int tr, int i, int d){ if (tl
8. Getting sum int sum(int v, int tl, int tr, int l, int r){ if (l >
9. Let’s make the task more difficult Запросы: 1) Изменить значение элементов [l;r] на d 2) Получить
10. struct Tree { vector t; vector add // array for method of “lazy propagation” int size;
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){
13. Getting sum int sum(int v, int tl, int tr, int l, int r){ if (l >
15. Скачать презентацию

Слайд 2

Слайд 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 <= 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];
}

Слайд 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 <= 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

Слайд 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
{
vector t;
vector add // array for method of “lazy propagation”
int

size;
void init(vector &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];
}
};

Слайд 11

The main function of the method
void push(int v){
add[2v]+= add[v];
add[2v+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);

Introduction to Segment tree

Содержание

The Basic idea of a segment tree

Рассмотрим пример реализации дерева отрезков для следующих запросов: 1) Добавить к i-му

Creating structurestruct Tree{ vector t; int size;};

Initialization of the tree void init(vector &a){ size = 1; while(size <= n) size

The change request void change(int v, int tl, int tr, int i,

Getting sum int sum(int v, int tl, int tr, int l, int

Let’s make the task more difficultЗапросы: 1) Изменить значение элементов [l;r] на

struct Tree{ vector t; vector add // array for method of “lazy propagation” int

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

The change request void change(int v, int tl, int tr, int l,

Getting sum int sum(int v, int tl, int tr, int l, int

Похожие презентации

Рассмотрим пример реализации дерева отрезков для следующих запросов:
1) Добавить к i-му

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

Initialization of the tree
void init(vector &a){
size = 1;
while(size <= n) size

The change request
void change(int v, int tl, int tr, int i,

Getting sum
int sum(int v, int tl, int tr, int l, int

Let’s make the task more difficult
Запросы:
1) Изменить значение элементов [l;r] на

struct Tree
{
vector t;
vector add // array for method of “lazy propagation”
int

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

The change request
void change(int v, int tl, int tr, int l,

Getting sum
int sum(int v, int tl, int tr, int l, int