Отложенное построение

Рассмотрим нашу любимую задачу суммы на подотрезках, но теперь все индексы лежат не в пределах $10^5$ или $10^6$, а до $10^9$ или даже $10^{18}$.

Все асимптотики нас по прежнему более-менее устраивают:

Единственная проблема — это этап построения, работающий за линейное от $n$ время и память.

Решить её можно отказавшись от явного создания всех вершин дерева в самом начале. Изначально создадим только лишь корень, а остальные вершины будем создавать на ходу, когда в них потребуется записать что-то не дефолтное — как в lazy propagation:

struct Segtree {
    int lb, rb;
    int s = 0;
    Segtree *l = 0, *r = 0;

    Segtree(int lb, int rb) : lb(lb), rb(rb) {
        // а тут ничего нет
    }

    // создает детей, если нужно
    void extend() {
        if (!l && lb + 1 < rb) {
            int t = (lb + rb) / 2;
            l = new segtree(lb, t);
            r = new segtree(t, rb);
        }
    }
    
    // ...
};

Теперь по аналогии с push будем в начале всех методов будем проверять, что дети-вершины созданы, и создавать их, если это не так.

void add(int k, int x) {
    extend();
    s += x;
    if (l) {
        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;
    extend();
    return l->sum(lq, rq) + r->sum(lq, rq);
}

Такой метод в основном приеним только к реализации на указателях, однако при использовании индексаций можно хранить вершины не в массиве, а в хеш-таблице: запросы станут работать дольше, но не асимптотически. Отметим также, что в любом случае на каждый запрос потребуется $O(\log n)$ дополнительной памяти для создания новых вершин, что обычно приводит к асимптотике $O(q \log n)$ по памяти.

Также, если все запросы известны заранее, то их координаты можно просто сжать перед обработкой запросов. Автор обычно делает это так:

vector<int> compress(vector<int> a) {
    vector<int> b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    for (int &x : a) 
        x = int(lower_bound(b.begin(), b.end(), x) - b.begin());
    return a;
}

В большинстве случаев, использовать динамическое построение — это как стрелять из пушки по воробьям. Попробуйте сначала более простые методы: возможно, всё просто в set влезает.