Дерево отрезков на указателях

В этой статье мы реализуем дерево отрезков для точечных изменений и суммы на отрезке. Наша первая реализация будет на указателях. Она не самая быстрая и компактная, но зато самая общая и понятная.

Замечание. Почти везде мы будем использовать полуинтервалы — обозначаемые как $[l, r)$ — вместо отрезков. Несмотря на контринтуитивность, это немного упростит код и вообще является хорошей практикой в программировании, подобно нумерации с нуля.

#Хранение в памяти

Каждая вершина дерева отрезков будет структурой, которая содержит ссылки на детей, свои границы $[l, r)$ и дополнительную нужную для задачи информацию — в нашем случае, сумму на отрезке.

Вершины будем создавать во время построения без какого-либо заданного порядка, поэтому ссылки на детей будут просто указателями на другую такую же структуру вершины-ребенка.

struct Segtree {
    int lb, rb; // левые и правые границы отрезков
    int s = 0; // сумма на текущем отрезке
    Segtree *l = 0, *r = 0; // указатели на детей (0 означает, что ребенка нет)
    
    Segtree(int lb, int rb) { /* конструктор: метод, вызывающийся при создании */ }
    void add(int k, int x) { /* отреагировать на a[k] += x */ }
    int sum(int lq, int rq) { /* вывести сумму [lq, rq) */ }
};

В олимпиадных задачах запросы часто подаются в формате «строка 0 k x для прибавления и 1 l r для суммы». Их можно парсить так:

int n, q;
cin >> n >> q;

Segtree s(0, n);

while (q--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t)
        s.add(x, y);
    else
        cout << s.sum(x, y) << endl;
}

Осталось собственно реализовать построение и запросы.

#Построение

Строить дерево отрезков можно рекурсивным конструктором, который создает детей, пока не доходит до листьев:

Segtree(int lb, int rb) : lb(lb), rb(rb) {
    if (lb + 1 < rb) {
        // если не лист, создаем детей
        int t = (lb + rb) / 2;
        l = new Segtree(lb, t);
        r = new Segtree(t, rb);
    }
}

Если изначально массив не нулевой, то можно параллельно с проведением ссылок насчитывать суммы:

Segtree(int lb, int rb) : lb(lb), rb(rb) {
    if (lb + 1 == rb)
        s = a[lb];
    else {
        int t = (lb + rb) / 2;
        l = new Segtree(lb, t);
        r = new Segtree(t, rb);
        s = l->s + r->s;
    }
}

Альтернативно, можно либо потом отдельно пройтись по массиву и добавить каждое число по отдельности.

#Изменение

Для запроса прибавления будем рекурсивно спускаться вниз, пока не дойдем до листа, соответствующего элементу $k$, и на всех промежуточных вершинах прибавим $x$:

void add(int k, int x) {
    s += x;
    // проверим, есть ли у нас дети:
    if (l) {
        // если k в левой половине
        if (k < l->rb)
            l->add(k, x);
        else
            r->add(k, x);
    }
}

#Сумма

Для суммы сложнее — нужно делать разбор случаев, как отрезок запроса пересекается с отрезком вершины:

int sum(int lq, int rq) {
    if (lb >= lq && rb <= rq)
        // если мы лежим полностью в отрезке запроса, вывести сумму
        return s;
    if (max(lb, lq) >= min(rb, rq))
        // если мы не пересекаемся с отрезком запроса, вывести ноль
        return 0;
    // иначе всё сложно -- запускаемся от детей и пусть они там сами решают
    return l->sum(lq, rq) + r->sum(lq, rq);
}

#Оптимизации

Данная реализация простая и расширяемая, но весьма неэффективная по времени и памяти, хотя ей можно сдать примерно 90% задач на олимпиадах по программированию.

Из относительно легких оптимизаций:

Можно не хранить границы отрезка lb и rb, а пересчитывать их во время спуска.
На 64-битных системах выгоднее использовать не new и указатели, а выделять вершины на массиве / векторе и использовать индексы относительно него: они будут весить 4 байта, а не 8.

Однако основная причина, почему реализация на указателях такая медленная, в том, что нужно много раз ходить по ссылкам, чтобы получать данные нужных вершин. Оказывается, можно избавиться от ссылок вообще, если ввести однозначную нумерацию вершин и расположить их в таком порядке на массиве — подробнее об этом можно почитать у Емакса и на CodeForces.