|
Дерево отрезков
Дерево отрезков - структура данных, предназначенная для быстрого выполнения запросов о состоянии какого-либо интервала последовательности.
Листинг C++
/*
Дерево отрезков
*/
class segments_tree
{
public:
int l, r;
int Max, Min, Sum;
int count_min, count_max;
int add;
segments_tree *left;
segments_tree *right;
segments_tree(int _l, int _r);
void modify(int _l, int _r, int value);
int maximum(int _l, int _r);
int minimum(int _l, int _r);
int sum(int _l, int _r);
int count_minimal(int _l, int _r);
int count_maximal(int _l, int _r);
};
// Конструктор дерева
segments_tree :: segments_tree(int _l, int _r)
{
l = _l;
r = _r;
Max = 0;
Min = 0;
Sum = 0;
count_min = (_r - _l + 1);
count_max = (_r - _l + 1);
add = 0;
left = NULL;
right = NULL;
if (l < r)
{
left = new segments_tree(l, (l + r) / 2);
right = new segments_tree((l + r) / 2 + 1, r);
}
}
// Добавление ко всем элементам с _l по _r числа value
void segments_tree :: modify(int _l, int _r, int value)
{
if (l == _l && r == _r)
add += value;
else
{
if (_l <= left->r)
left->modify(_l, min(_r, left->r), value);
if (_r >= right->l)
right->modify(max(_l, right->l), _r, value);
Max = max(left->Max + left->add, right->Max + right->add);
Min = min(left->Min + left->add, right->Min + right->add);
Sum = left->Sum + left->add * (left->r - left->l + 1) +
right->Sum + right->add * (right->r - right->l + 1);
count_min = 0;
if (left->Min + left->add == Min)
count_min += left->count_min;
if (right->Min + right->add == Min)
count_min += right->count_min;
count_max = 0;
if (left->Max + left->add == Max)
count_max += left->count_max;
if (right->Max + right->add == Max)
count_max += right->count_max;
}
}
// Максимальное число из [_l, _r]
int segments_tree :: maximum(int _l, int _r)
{
if (l == _l && r == _r)
return Max + add;
int res = - 1e7;
if (_l <= left->r)
res = max(res, left->maximum(_l, min(_r, left->r)) + add);
if (_r >= right->l)
res = max(res, right->maximum(max(_l, right->l), _r) + add);
return res;
}
// Минимальное число из [_l, _r]
int segments_tree :: minimum(int _l, int _r)
{
if (l == _l && r == _r)
return Min + add;
int res = 1e7;
if (_l <= left->r)
res = min(res, left->minimum(_l, min(_r, left->r)) + add);
if (_r >= right->l)
res = min(res, right->minimum(max(_l, right->l), _r) + add);
return res;
}
// Сумма всех чисел из [_l, _r]
int segments_tree :: sum(int _l, int _r)
{
if (l == _l && r == _r)
return Sum + add * (_r - _l + 1);
int res = 0;
if (_l <= left->r)
res += left->sum(_l, min(_r, left->r));
if (_r >= right->l)
res += right->sum(max(_l, right->l), _r);
return res + add * (_r - _l + 1);
}
// Количество минимальных элементов в [_l, _r]
int segments_tree :: count_minimal(int _l, int _r)
{
if (l == _l && r == _r)
return count_min;
int res = 0;
if (_l <= left->r && left->Min + left->add == Min)
res += left->count_minimal(_l, min(_r, left->r));
if (_r >= right->l && right->Min + right->add == Min)
res += right->count_minimal(max(_l, right->l), _r);
return res;
}
// Количество максимальных элементов в [_l, _r]
int segments_tree :: count_maximal(int _l, int _r)
{
if (l == _l && r == _r)
return count_max;
int res = 0;
if (_l <= left->r && left->Max + left->add == Max)
res += left->count_maximal(_l, min(_r, left->r));
if (_r >= right->l && right->Max + right->add == Max)
res += right->count_maximal(max(_l, right->l), _r);
return res;
}
Создан 09.12.2007, 19:44
Изменён 15.01.2011, 18:46
По всем вопросам обращаться: rumterg@gmail.com