#	User	Rating
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

#	User	Contrib.
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] не составит большого труда. А функции в основном решении уже стоят где надо и с правильными параметрами.