№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Привет, Codeforces!

В этом посте я бы хотел поделиться тем, как я пишу Дерево отрезков, объясню, почему я это делаю классом, а так же какие у этого плюсы и минусы.
Чтобы не быть голословным я бы хотел рассмотреть свое решение на конкретной задаче (осторожно, идеи к решению)

Код

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef pair<int, int> pii;
#define vec vector
//END

class SegTree {
    int n;
    vec<pii> t;
    vec<int> p;
    vec<int> a;
    pii mrg(pii a, pii b) {
        return {a.first + b.first, a.second + b.second};
    }
    void build(int v, int l, int r) {
        if (l == r - 1) {
            if (a[l]) {
                t[v] = {1, 0};
            } else {
                t[v] = {0, 1};
            }
            return;
        }
        int m = (r + l) / 2;
        build(2 * v + 1, l, m);
        build(2 * v + 2, m, r);
        t[v] = mrg(t[2 * v + 1], t[2 * v + 2]);
    }
    void push(int v, int l, int r) {
        if (p[v]) {
            swap(t[v].second, t[v].first);
        }
        if (l != r - 1) {
            p[2 * v + 1] ^= p[v];
            p[2 * v + 2] ^= p[v];
        }
        p[v] = 0;
    }
    void upd(int v, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            p[v] ^= 1;
            push(v, l, r);
            return;
        }
        push(v, l, r);
        if (R <= l || r <= L) {
            return;
        }
        int m = (r + l) / 2;
        upd(2 * v + 1, l, m, L, R);
        upd(2 * v + 2, m, r, L, R);
        t[v] = mrg(t[2 * v + 1], t[2 * v + 2]);
    }
    int get(int v, int l, int r, int L, int R) {
        push(v, l, r);
        if (L <= l && r <= R) {
            return t[v].first;
        }
        if (R <= l || r <= L) {
            return 0;
        }
        int m = (r + l) / 2;
        int a = get(2 * v + 1, l, m, L, R);
        int b = get(2 * v + 2, m, r, L, R);
        return a + b;
    }

public:
    SegTree(vec<int> &a) : a(a) {
        n = a.size();
        t.resize(4 * n);
        p.resize(4 * n);
        if (n) {
            build(0, 0, n);
        }
    }
    int get(int l, int r) {
        if (n == 0) return 0;
        return get(0, 0, n, l, r);
    }
    void upd(int l, int r) {
        if (n == 0) return;
        upd(0, 0, n, l, r);
    }
    
};

void solve() {
    //code here
    int n, m;
    cin >> n >> m;
    vec<int> a, b;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (i % 2) {
            b.push_back(x);
        } else {
            a.push_back(x);
        }
    }
    SegTree sga(a), sgb(b);
    for (int i = 0; i < m; ++i) {
        int t, l, r;
        cin >> t >> l >> r;
        l--;
        r--;
        int l1, r1, l2, r2;
        l1 = (l + 1) / 2;
        r1 = r / 2;
        r2 = (r - 1) / 2;
        if (l % 2) {
            l2 = (l) / 2;
            
        } else {
            l2 = (l + 1) / 2;
        }
        if (t == 1) {
            if (l % 2) {
                sgb.upd(l2, r2 + 1);
            } else {
                sga.upd(l1, r1 + 1);
            }
        } else {
            int cnt = sga.get(l1, r1 + 1) + sgb.get(l2, r2 + 1);
            cout << cnt << '\n';
        }
    }
    //
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    //    cin >> tt;
    for (int req = 0; req < tt; ++req) {
        unsigned start = clock();
        solve();
        cout << '\n';
        unsigned end = clock();
        cerr << "WorkTime: " << (end - start) / (double) CLOCKS_PER_SEC << '\n';
    }
}

Решение

Что в этом написании особенного

Основная моя идея в том, чтобы реализовать ДО как класс

Это позволяет использовать для двух деревьев отрезков более понятный интерфейс sgb.upd(l2, r2 + 1) sga.upd(l1, r1 + 1) sga.get(l1, r1 + 1) + sgb.get(l2, r2 + 1) вместо upd1(l1, r1 +1) upd2(l2, r2 + 1) и get1(l1, r1 + 1) + get2(l2, r2 + 1) А если количество деревьев переменно, то по другому это вроде не закодить(по крайней мере я не умею).

Другая не менее важная идея состоит в том, чтобы реализовать две функции каждого типа например get(int v, int l, int r, int L, int R) и get(int L, int R)

Я хочу получить значение на отрезке и не хочу думать о параметрах которые не влияют на запрос. Поэтому get(int v, int l, int r, int L, int R) является внутренним интерфейсом, который используется только для подсчета результата и не вызывается снаружи.

Так же я использую структуру, которая поддерживает приватные и публичные поля.

Это чисто эстетическое предпочтение, когда редактор подсказывает только те функции, которые могут быть вызваны снаружи. против

Почему я пишу именно так

Однажды, когда я писал отбор в сириус, была задача в которой n исходная и n ДО не совпадали. И в функции запросов и обновления я писал неверное значение n. За время отбора я так и не раздебагал это. Как итог мне не хватило совсем чуть чуть баллов до прохода. После этой грустной истории я разработал для себя некий стандарт, которому стараюсь соответствовать.

Заключение

Плюсы

Помогает не думать над тем, какой параметр передавать в запрос (Например в приведенной выше задаче, в одном случае размер равен n/2 + 1 а в другом n/2. Подобная ошибка в пару символов может стоить нескольких минут, а в худшем случае и десятков).
Эстетично приятно.
Пишется шаблонно (сначала mrg, потом build, дальше push и тд).
Легко заменить. Нужно только изменить функцию mrg и поля у вершины.
Подходит для задач, где нужно одинаковое ДО для нескольких массивов

Минусы

Дольше работает. Во-первых, как известно статмасивы всегда лучше векторов по скорости, однако создать класс со статмасивом лично у меня не получилось (код крашается). Во-вторых вызов функции из класса вроде работает дольше, чем обычной функции
Дольше пишется.

Вывод

Объективно минусы существенные по сравнению с плюсами. Однако я считаю, что мой способ написания имеет место быть. Он помогает избежать ошибок при написании и использовании не очень внимательным людям (к которым я, конечно же, отношусь). Если решение получает TL заменить vec t; на pii t[MAXN] не составит большого труда. А функции в основном решении уже стоят где надо и с правильными параметрами.

Я никого не призываю начинать писать код по другому. Лишь хочу поделиться своими знаниями. Спасибо за внимание, и высокого рейтинга!

Комментарии (21)

Написать комментарий?

Death_on_2_Legs

3 года назад, # |

-20

Если писать ДО снизу то такой проблемы не будет

→ Ответить

saprykin

3 года назад, # ^ |

-11

Какой "такой"? Если тебе надо будет использовать несколько до, то все равно придется писать класс, разве нет?

devid

Нет, ты что, просто напиши функции get1 get2 get3 add1 add2 add3 pushlol pushkek pushamogus

FairyWinx

-8

Я так делал до 10 класса, кста

Igorbunov

Я вот все ещё так делаю)

Игорь, я твой фанат!!!!!!!

-13

Он Иван)

В никнейме написано Игорь, значит Игорь!!!!

Кек, че вы минусите. Зайдите на его профиль и посмотрите

Тебя на литературе учили определению иронии?

Ormlis

Почему ты не пишешь отдельный класс для вершины в ДО?

Вообще если для вершины нужно >2 полей то пишу структуру. Здесь было лень)

Ну все, слился получается

Виноват

163onmyneck

← Rev. 3 →

можно же писать так:

int get(int l, int r, int x = 1, int lx = 0, int rx = sz) {
    if (l >= rx || lx >= r) return 0;
    if (l <= lx && rx <= r) return t[x];
    int m = (lx + rx) >> 1;
    return get(l, r, x << 1, lx, m) + get(l, r, x << 1 | 1, m, rx);
}

ну конечно если нужно только одно ДО

А чему sz равно? Если это не константа, то не получится

Хотя если до одно, то скорее всего размер действительно почти всегда константный. Просто если есть способ писать всегда одинаково, то почему бы и нет

ну я пишу как на кф еду, sz = 1 << (ceil(log(n) / log(2))

Я посмотрел твою посылку 125408125. Такое не работает в классах, к сожалению.

oversolver

Поздравляю. Осталось переделать на любой тип, научится передавать merge и подобное, и избавиться от 4 * n, и будет дефолт.

P. S. ...статмасивы всегда лучше векторов по скорости — откуда инфа?

Опыт + информация от других. Могу привести код в котором переписывание вектора на статмасив ускорило почти в 2 раза код(но речь не про до совсем)