Иногда я задумываюсь, какую реализацию дерева отрезков написать в задаче. Обычно я при помощи метода "пальцем в небо" выбираю какую-то и в большинстве случаев она проходит ограничения.↵
↵
Я решил подвести основу, так сказать базу, под этот выбор и протестировал на производительность 4 разные реализации:↵
<ul>↵
<li>↵
Простой рекурсивный "Разделяй и властвуй"↵
↵
<spoiler summary="Код">↵
~~~↵
struct SimpleRecursiveSegmentTree {↵
unsigned size;↵
↵
private:↵
std::vector<long long> t;↵
↵
void _build(const std::vector<int> &v, unsigned p, unsigned l, unsigned r) {↵
if (r == l + 1) {↵
t[p] = v[l];↵
return;↵
}↵
unsigned m = (l + r) / 2;↵
_build(v, 2 * p + 1, l, m);↵
_build(v, 2 * p + 2, m, r);↵
t[p] = t[2 * p + 1] + t[2 * p + 2];↵
}↵
↵
long long _get(unsigned p, unsigned l, unsigned r, unsigned a,↵
unsigned b) const {↵
if (b <= l || r <= a) {↵
return 0LL;↵
}↵
if (a <= l && r <= b) {↵
return t[p];↵
}↵
unsigned m = (l + r) / 2;↵
return _get(2 * p + 1, l, m, a, b) + _get(2 * p + 2, m, r, a, b);↵
}↵
↵
void _add(unsigned p, unsigned l, unsigned r, unsigned i, int x) {↵
if (i < l || r <= i) {↵
return;↵
}↵
if (r == l + 1) {↵
t[p] += x;↵
return;↵
}↵
unsigned m = (l + r) / 2;↵
_add(2 * p + 1, l, m, i, x);↵
_add(2 * p + 2, m, r, i, x);↵
t[p] = t[2 * p + 1] + t[2 * p + 2];↵
}↵
↵
public:↵
SimpleRecursiveSegmentTree(unsigned _size) noexcept : size(_size) {↵
t.resize(4 * size);↵
}↵
↵
SimpleRecursiveSegmentTree(const std::vector<int> &v) noexcept↵
: size(v.size()) {↵
t.resize(4 * size);↵
_build(v, 0, 0, size);↵
}↵
↵
void add(unsigned i, int x) { _add(0, 0, size, i, x); }↵
↵
long long get(unsigned l, unsigned r) const {↵
return _get(0, 0, size, l, r);↵
}↵
};↵
~~~↵
</spoiler>↵
↵
</li>↵
<li>↵
Оптимизированный рекурсивный "Разделяй и властвуй", который не спускается в заведомо ненужных сыновей.↵
↵
<spoiler summary="Код">↵
~~~↵
struct OptimizedRecursiveSegmentTree {↵
unsigned size;↵
↵
private:↵
std::vector<long long> t;↵
↵
void _build(const std::vector<int> &v, unsigned p, unsigned l, unsigned r) {↵
if (r == l + 1) {↵
t[p] = v[l];↵
return;↵
}↵
unsigned m = (l + r) / 2;↵
_build(v, 2 * p + 1, l, m);↵
_build(v, 2 * p + 2, m, r);↵
t[p] = t[2 * p + 1] + t[2 * p + 2];↵
}↵
↵
long long _get(unsigned p, unsigned l, unsigned r, unsigned a,↵
unsigned b) const {↵
if (a <= l && r <= b) {↵
return t[p];↵
}↵
unsigned m = (l + r) / 2;↵
long long res = 0;↵
if (a < m) {↵
res += _get(2 * p + 1, l, m, a, b);↵
}↵
if (b > m) {↵
res += _get(2 * p + 2, m, r, a, b);↵
}↵
return res;↵
}↵
↵
void _add(unsigned p, unsigned l, unsigned r, unsigned i, int x) {↵
if (r == l + 1) {↵
t[p] += x;↵
return;↵
}↵
unsigned m = (l + r) / 2;↵
if (i < m) {↵
_add(2 * p + 1, l, m, i, x);↵
} else {↵
_add(2 * p + 2, m, r, i, x);↵
}↵
t[p] = t[2 * p + 1] + t[2 * p + 2];↵
}↵
↵
public:↵
OptimizedRecursiveSegmentTree(unsigned _size) noexcept : size(_size) {↵
t.resize(4 * size);↵
}↵
↵
OptimizedRecursiveSegmentTree(const std::vector<int> &v) noexcept↵
: size(v.size()) {↵
t.resize(4 * size);↵
_build(v, 0, 0, size);↵
}↵
↵
void add(unsigned i, int x) { _add(0, 0, size, i, x); }↵
↵
long long get(unsigned l, unsigned r) const {↵
return _get(0, 0, size, l, r);↵
}↵
};↵
~~~↵
</spoiler>↵
↵
</li>↵
<li>↵
Нерекурсивная реализация (взял отсюда: https://mirror.codeforces.com/blog/entry/18051)↵
↵
<spoiler summary="Код">↵
~~~↵
struct NonRecursiveSegmentTree {↵
unsigned size;↵
↵
private:↵
std::vector<long long> t;↵
↵
void _build(const std::vector<int> &v) {↵
std::copy(v.begin(), v.end(), t.begin() + size);↵
for (int i = size - 1; i > 0; --i) {↵
t[i] = t[i * 2] + t[i * 2 ^ 1];↵
}↵
}↵
↵
public:↵
NonRecursiveSegmentTree(unsigned _size) noexcept : size(_size) {↵
t.resize(2 * size);↵
}↵
↵
NonRecursiveSegmentTree(const std::vector<int> &v) noexcept↵
: size(v.size()) {↵
t.resize(2 * size);↵
_build(v);↵
}↵
↵
void add(unsigned i, int x) {↵
i += size;↵
for (t[i] += x; i > 1; i /= 2) {↵
t[i / 2] = t[i] + t[i ^ 1];↵
}↵
}↵
↵
long long get(unsigned l, unsigned r) const {↵
long long res = 0;↵
for (l += size, r += size; l < r; l /= 2, r /= 2) {↵
if (l & 1) {↵
res += t[l++];↵
}↵
if (r & 1) {↵
res += t[--r];↵
}↵
}↵
return res;↵
}↵
};↵
~~~↵
</spoiler>↵
↵
</li>↵
<li>↵
Дерево Фенвика↵
↵
<spoiler summary="Код">↵
~~~↵
struct FenwickTree {↵
unsigned size;↵
↵
private:↵
std::vector<long long> t;↵
↵
long long get_prefix(int i) const {↵
long long res = 0;↵
while (i >= 0) {↵
res += t[i];↵
i = (i & (i + 1)) - 1;↵
}↵
return res;↵
}↵
↵
public:↵
void add(unsigned i, int x) {↵
while (i < size) {↵
t[i] += x;↵
i = i | (i + 1);↵
}↵
}↵
↵
FenwickTree(unsigned _size) : size(_size) { t.resize(size); }↵
↵
FenwickTree(const std::vector<int> &v) : size(v.size()) {↵
t.resize(size);↵
for (unsigned i = 0; i < size; ++i) {↵
add(i, v[i]);↵
}↵
}↵
↵
long long get(unsigned l, unsigned r) {↵
return get_prefix((int)r - 1) - get_prefix((int)l - 1);↵
}↵
};↵
~~~↵
</spoiler>↵
↵
</li>↵
</ul>↵
↵
Все реализации поддерживают такие запросы:↵
<ul>↵
<li>↵
`get(l, r)`: сумма на отрезке (полуинтервале) $[l; r)$↵
</li>↵
<li>↵
`update(i, x)`: прибавление к элементу под индексом $i$ числа $x$↵
</li>↵
</ul>↵
↵
Вот результаты:↵
↵
↵
↵
Примечание: я старался не делать никаких оптимизаций, требовательных к конкретным запросам, чтобы с небольшими изменениями структуры данных могли применяться для любых операций.↵
↵
Я генерировал запросы следующим образом:↵
↵
- Прибавление в точке: случайный индекс (`rnd() % size`) и случайное число↵
- Сумма на отрезке: сначала, генерируется длина отрезка (`rnd() % size + 1`), затем подходящая левая граница.↵
↵
↵
[Исходники бенчмарка](https://gist.github.com/pavel-the-best/35e1bf7759152c442f3c83d721947e97#file-bench-cpp). Примечание: желательно отключить CPU frequency scaling и закрыть все приложения, которые могут мешать бенчмарку (чем больше закроете -- тем в теории стабильнее будет результат).↵
↵
[Скрипт на Python, создающий красивый график](https://gist.github.com/pavel-the-best/8636aeb68db2119b00fce679d361df6f#file-generate_plot-py)↵
↵
[Результаты в формате JSON](https://gist.github.com/pavel-the-best/f33879ea075b5e9b3ea16e4d85d807dd) на случай, если Вы захотите ещё поиграться с данными.↵
↵
Я компилировал бенчмарк с `#pragma GCC optimize("O3")` на GNU GCC 11.3.0 и запускал его с фиксированной частотой процессора 2.4 GHz.↵
↵
Наверное, это мой первый вклад в сообщество, поэтому любые дополнения/предложения приветствуются.
↵
Я решил подвести основу, так сказать базу, под этот выбор и протестировал на производительность 4 разные реализации:↵
<ul>↵
<li>↵
Простой рекурсивный "Разделяй и властвуй"↵
↵
<spoiler summary="Код">↵
~~~↵
struct SimpleRecursiveSegmentTree {↵
unsigned size;↵
↵
private:↵
std::vector<long long> t;↵
↵
void _build(const std::vector<int> &v, unsigned p, unsigned l, unsigned r) {↵
if (r == l + 1) {↵
t[p] = v[l];↵
return;↵
}↵
unsigned m = (l + r) / 2;↵
_build(v, 2 * p + 1, l, m);↵
_build(v, 2 * p + 2, m, r);↵
t[p] = t[2 * p + 1] + t[2 * p + 2];↵
}↵
↵
long long _get(unsigned p, unsigned l, unsigned r, unsigned a,↵
unsigned b) const {↵
if (b <= l || r <= a) {↵
return 0LL;↵
}↵
if (a <= l && r <= b) {↵
return t[p];↵
}↵
unsigned m = (l + r) / 2;↵
return _get(2 * p + 1, l, m, a, b) + _get(2 * p + 2, m, r, a, b);↵
}↵
↵
void _add(unsigned p, unsigned l, unsigned r, unsigned i, int x) {↵
if (i < l || r <= i) {↵
return;↵
}↵
if (r == l + 1) {↵
t[p] += x;↵
return;↵
}↵
unsigned m = (l + r) / 2;↵
_add(2 * p + 1, l, m, i, x);↵
_add(2 * p + 2, m, r, i, x);↵
t[p] = t[2 * p + 1] + t[2 * p + 2];↵
}↵
↵
public:↵
SimpleRecursiveSegmentTree(unsigned _size) noexcept : size(_size) {↵
t.resize(4 * size);↵
}↵
↵
SimpleRecursiveSegmentTree(const std::vector<int> &v) noexcept↵
: size(v.size()) {↵
t.resize(4 * size);↵
_build(v, 0, 0, size);↵
}↵
↵
void add(unsigned i, int x) { _add(0, 0, size, i, x); }↵
↵
long long get(unsigned l, unsigned r) const {↵
return _get(0, 0, size, l, r);↵
}↵
};↵
~~~↵
</spoiler>↵
↵
</li>↵
<li>↵
Оптимизированный рекурсивный "Разделяй и властвуй", который не спускается в заведомо ненужных сыновей.↵
↵
<spoiler summary="Код">↵
~~~↵
struct OptimizedRecursiveSegmentTree {↵
unsigned size;↵
↵
private:↵
std::vector<long long> t;↵
↵
void _build(const std::vector<int> &v, unsigned p, unsigned l, unsigned r) {↵
if (r == l + 1) {↵
t[p] = v[l];↵
return;↵
}↵
unsigned m = (l + r) / 2;↵
_build(v, 2 * p + 1, l, m);↵
_build(v, 2 * p + 2, m, r);↵
t[p] = t[2 * p + 1] + t[2 * p + 2];↵
}↵
↵
long long _get(unsigned p, unsigned l, unsigned r, unsigned a,↵
unsigned b) const {↵
if (a <= l && r <= b) {↵
return t[p];↵
}↵
unsigned m = (l + r) / 2;↵
long long res = 0;↵
if (a < m) {↵
res += _get(2 * p + 1, l, m, a, b);↵
}↵
if (b > m) {↵
res += _get(2 * p + 2, m, r, a, b);↵
}↵
return res;↵
}↵
↵
void _add(unsigned p, unsigned l, unsigned r, unsigned i, int x) {↵
if (r == l + 1) {↵
t[p] += x;↵
return;↵
}↵
unsigned m = (l + r) / 2;↵
if (i < m) {↵
_add(2 * p + 1, l, m, i, x);↵
} else {↵
_add(2 * p + 2, m, r, i, x);↵
}↵
t[p] = t[2 * p + 1] + t[2 * p + 2];↵
}↵
↵
public:↵
OptimizedRecursiveSegmentTree(unsigned _size) noexcept : size(_size) {↵
t.resize(4 * size);↵
}↵
↵
OptimizedRecursiveSegmentTree(const std::vector<int> &v) noexcept↵
: size(v.size()) {↵
t.resize(4 * size);↵
_build(v, 0, 0, size);↵
}↵
↵
void add(unsigned i, int x) { _add(0, 0, size, i, x); }↵
↵
long long get(unsigned l, unsigned r) const {↵
return _get(0, 0, size, l, r);↵
}↵
};↵
~~~↵
</spoiler>↵
↵
</li>↵
<li>↵
Нерекурсивная реализация (взял отсюда: https://mirror.codeforces.com/blog/entry/18051)↵
↵
<spoiler summary="Код">↵
~~~↵
struct NonRecursiveSegmentTree {↵
unsigned size;↵
↵
private:↵
std::vector<long long> t;↵
↵
void _build(const std::vector<int> &v) {↵
std::copy(v.begin(), v.end(), t.begin() + size);↵
for (int i = size - 1; i > 0; --i) {↵
t[i] = t[i * 2] + t[i * 2 ^ 1];↵
}↵
}↵
↵
public:↵
NonRecursiveSegmentTree(unsigned _size) noexcept : size(_size) {↵
t.resize(2 * size);↵
}↵
↵
NonRecursiveSegmentTree(const std::vector<int> &v) noexcept↵
: size(v.size()) {↵
t.resize(2 * size);↵
_build(v);↵
}↵
↵
void add(unsigned i, int x) {↵
i += size;↵
for (t[i] += x; i > 1; i /= 2) {↵
t[i / 2] = t[i] + t[i ^ 1];↵
}↵
}↵
↵
long long get(unsigned l, unsigned r) const {↵
long long res = 0;↵
for (l += size, r += size; l < r; l /= 2, r /= 2) {↵
if (l & 1) {↵
res += t[l++];↵
}↵
if (r & 1) {↵
res += t[--r];↵
}↵
}↵
return res;↵
}↵
};↵
~~~↵
</spoiler>↵
↵
</li>↵
<li>↵
Дерево Фенвика↵
↵
<spoiler summary="Код">↵
~~~↵
struct FenwickTree {↵
unsigned size;↵
↵
private:↵
std::vector<long long> t;↵
↵
long long get_prefix(int i) const {↵
long long res = 0;↵
while (i >= 0) {↵
res += t[i];↵
i = (i & (i + 1)) - 1;↵
}↵
return res;↵
}↵
↵
public:↵
void add(unsigned i, int x) {↵
while (i < size) {↵
t[i] += x;↵
i = i | (i + 1);↵
}↵
}↵
↵
FenwickTree(unsigned _size) : size(_size) { t.resize(size); }↵
↵
FenwickTree(const std::vector<int> &v) : size(v.size()) {↵
t.resize(size);↵
for (unsigned i = 0; i < size; ++i) {↵
add(i, v[i]);↵
}↵
}↵
↵
long long get(unsigned l, unsigned r) {↵
return get_prefix((int)r - 1) - get_prefix((int)l - 1);↵
}↵
};↵
~~~↵
</spoiler>↵
↵
</li>↵
</ul>↵
↵
Все реализации поддерживают такие запросы:↵
<ul>↵
<li>↵
`get(l, r)`: сумма на отрезке (полуинтервале) $[l; r)$↵
</li>↵
<li>↵
`update(i, x)`: прибавление к элементу под индексом $i$ числа $x$↵
</li>↵
</ul>↵
↵
Вот результаты:↵
↵
↵
↵
Примечание: я старался не делать никаких оптимизаций, требовательных к конкретным запросам, чтобы с небольшими изменениями структуры данных могли применяться для любых операций.↵
↵
Я генерировал запросы следующим образом:↵
↵
- Прибавление в точке: случайный индекс (`rnd() % size`) и случайное число↵
- Сумма на отрезке: сначала, генерируется длина отрезка (`rnd() % size + 1`), затем подходящая левая граница.↵
↵
↵
[Исходники бенчмарка](https://gist.github.com/pavel-the-best/35e1bf7759152c442f3c83d721947e97#file-bench-cpp). Примечание: желательно отключить CPU frequency scaling и закрыть все приложения, которые могут мешать бенчмарку (чем больше закроете -- тем в теории стабильнее будет результат).↵
↵
[Скрипт на Python, создающий красивый график](https://gist.github.com/pavel-the-best/8636aeb68db2119b00fce679d361df6f#file-generate_plot-py)↵
↵
[Результаты в формате JSON](https://gist.github.com/pavel-the-best/f33879ea075b5e9b3ea16e4d85d807dd) на случай, если Вы захотите ещё поиграться с данными.↵
↵
Я компилировал бенчмарк с `#pragma GCC optimize("O3")` на GNU GCC 11.3.0 и запускал его с фиксированной частотой процессора 2.4 GHz.↵
↵
Наверное, это мой первый вклад в сообщество, поэтому любые дополнения/предложения приветствуются.
