AI Arbori de Intervale
Motivaţia Ideea generală Implementarea Practice
AI Arbori de Intervale
Motivaţia Ideea generală Implementarea Practice

Update în $O(\log_2 n)$

× 
void update(int node, int left, int right, int pos, int val) {
    // Ne aflam in intervalul [left, right].
    if (left == right) { // Daca am ajuns pe pozitia pos,
        tree[node] = val; // schimbam valoarea de pe pozitia pos in val.
        return;
    }

    int mid = (left + right) / 2; // Impartim intervalul curent in doua jumatati.
    if (pos <= mid) // Daca pozitia pos se afla in primul interval, [left, mid]:
        update(2 * node, left, mid, pos, val);
    else // Daca pozitia pos se afla in al doilea interval, [mid + 1, right]:
        update(2 * node + 1, mid + 1, right, pos, val);

    // Cand am revenit, recalculam suma pe intervalul [left, right],
    // insumand sumele deja calculate pe intervalele [left, mid] si [mid + 1, right]:
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

Instrucţiune:

  • update(pos, val);


Query în $O(\log_2 n)$

× 
int query(int node, int left, int right, int x, int y) {
    // Ne aflam in intervalul [left, right].
    if(x <= left && right <= y) // Daca intervalul in care ne aflam e cuprins in intervalul cautat
       return tree[node]; // returnam suma intervalului [left, right].

    int mid = (left + right) / 2; // Impartim intervalul curent in doua jumatati.
    int ans1 = 0, ans2 = 0;

    if(x <= mid) // Daca exista elemente din intervalul cautat in [left, mid]:
       ans1 = query(2 * node, left, mid, x, y);
    if(y > mid) // Daca exista elemente din intervalul cautat in [mid + 1, right]:
       ans2 = query(2 * node + 1, mid + 1, right, x, y);
    // Cand am revenit, returnam suma elementelor care se afla in intervalul [left, right],
    // Insumand suma elementelor cautate din intervalele [left, mid] si [mid + 1, right]:
    return ans1 + ans2;
}

Instrucţiune:

  • query(left, right);


Build în $O(n)$

× 
void build(int node, int left, int right){
    // Ne aflam in intervalul [left, right].
    if(left == right){ // Daca nodul curent e o frunza,
       tree[node] = v[left]; // Punem in nod valoarea pozitiei st
       return;
    }
    int mid = (left + right) / 2; // Impartim intervalul curent in doua jumatati.
    build(2 * node, left, mid); // Calculam suma elementelor din intervalul [left, mid]
    build(2 * node + 1, mid + 1, right); // Calculam suma elementelor din intervalul [mid +1, right]
    // Cand am revenit, calculam suma pe intervalul [left, right],
    // insumand sumele deja calculate pe intervalele [left, mid] si [mid + 1, right]:
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

Instrucţiune:

  • build([val1, val2, ..., valN]);


Update cu lazy în $O(\log_2 n)$

× 
void update(int node, int left, int right, int x, int y, int val){
    // Ne aflam in intervalul [left, right].
    // Fiecare pozitie din intervalul [x, y] creste cu valoarea val
    int mid = (left + right) / 2; // Impartim intervalul curent in doua jumatati.
    if(lazy[node] && left != right){ // Daca exista lazy si nodul curent nu este o frunza
       lazy[2 * node] += lazy[node] * (mid - left +1); // Propagam lazy-ul la cei 2 fii
       lazy[2 * node + 1] += lazy[node] * (right - mid);
       tree[2 * node] += lazy[node];
       tree[2 * node + 1] += lazy[node];
       lazy[node] = 0; // Dupa propagare lazy-ul nodului devine 0
    }
    if(x <= left && right <= y){ // Daca intervalul in care ne aflam e cuprins in intervalul cautat
       lazy[node] += val; // Ca sa nu trecem la fiecare pozitie in parte din intervalul [left, right]
       tree[node] += val * (dr - st +1); // Retinem ca trebuie sa crestem fiecare valoare 
       // de pe pozitiile din intervalul [left, right] cu valoarea val
       return;
    }
    if(x <= mid)
       update(2 * node, left, mid, x, y, val);
    if(y > mid)
       update(2 * node + 1, mid + 1, right, x, y, val);
    // Cand am revenit, recalculam suma pe intervalul [left, right],
    // insumand sumele deja calculate pe intervalele [left, mid] si [mid + 1, right]:   
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

Query cu lazy în $O(\log_2 n)$

× 
int query(int node, int left, int right, int x, int y){
    // Ne aflam in intervalul [left, right].
    int mid = (left + right) / 2; // Impartim intervalul curent in doua jumatati.
    if(lazy[node] && left != right){ // Daca exista lazy si nodul curent nu este o frunza
       lazy[2 * node] += lazy[node] * (mid - left +1); // Propagam lazy-ul la cei 2 fii
       lazy[2 * node + 1] += lazy[node] * (right - mid);
       tree[2 * node] += lazy[node];
       tree[2 * node + 1] += lazy[node];
       lazy[node] = 0; // Dupa propagare lazy-ul nodului devine 0
    }
    if(x <= left && right <= y) // Daca intervalul in care ne aflam e cuprins in intervalul cautat
       return tree[node]; // returnam suma intervalului [left, right].
    int ans1 = 0, ans2 = 0;
    if(x <= mid) // Daca exista elemente din intervalul cautat in [left, mid]:
       ans1 = query(2 * node, left, mid, x, y); 
    if(y > mid) // Daca exista elemente din intervalul cautat in [mid + 1, right]:
       ans2 = query(2 * node + 1, mid + 1, right, x, y);
    // Cand am revenit, returnam suma elementelor care se afla in intervalul [left, right],
    // Insumand suma elementelor cautate din intervalele [left, mid] si [mid + 1, right]:   
    return ans1 + ans2;
}


Instrucțiuni:

  • build([val1, val2, ..., valN]);
  • update(pos, val);
  • query(left, right);