Доброго времени суток!

Я так понимаю вы храните дерево в виде обычного массива. создайте структуру node, в которой объявите значение и указатели на левого и правого потомка, а при обращении к ним создавайте их

В обычном дереве отрезке потомками вершины V будут V+V и V+V+1.
Но в неявном ДО изначально у нас нету потомков, мы их дальше по ходу программы будем создавать. Для каждой вершины будем хранить номер его левого и правого потомка(0 если не существует). Если во время обновления потомка не существует то создаем его, а если в функции get не существует потомка то просто не будем туда спускатся(так как там мы все равно ничего не найдем).
Реализация update

int cnt = 1;//количество созданных вершин
void upd(int id, long long x, int v=1, int l=0, int r=INF){
    if(l>r) return;
    if(l == r){
        t[v] = x;
        return;
    }
    int mid = (l+r) / 2;
    if(id <= mid){
        if(!L[v]) L[v] = ++cnt; //если не существует левого сына, создаем
        upd(id, x, L[v], l, mid);
    }
    else{
        if(!R[v]) R[v] = ++cnt;
        upd(id, x, R[v], mid+1, r);
    }
    t[v] = t[L[v]] + t[R[v]];
}

Реализация get(в этом случае сумма)

long long get(int l, int r, int v=1, int tl=0, int tr=INF){
    if(!v || l>r || tl>tr || tl > r || tr < l) return 0;
    if(l <= tl && tr <= r) return t[v];
    int mid = (tl+tr) / 2;
    return get(l, r, L[v], tl, mid) + get(l, r, R[v], mid+1, tr);
}

Каждая функция создает максимум LogN дополнительной памяти.

"керево доторый"?