Arbori de intervale. Implementare si aplicatii.

Se considera urmatoarea cerinta: avem un tablou unidimensional cu n elemente, asupra acestuia se fac doua tipuri de operatii:
1.Update(x, y), elementul de la pozitia x primeste valoarea y.
2.Suma[ST, DR], adica suma elementelor din a cu indicele i, ST≤i≤DR
Prima metoda, elementara, poate solutiona fiecare query de tip suma in O(n) timp si update in O(1) timp, parcurgand efectiv elementele din intervalul dat de query-ul SUMA.
O a doua metoda se bazeaza pe algoritmul de Square Root Decomposition (cunoscut si ca Smenul lui Batog, atat Infoarena, cat si GeeksForGeeks au articole ce explica rationamentul si implementarea). Astfel, complexitatea de timp scade la O(sqrt(n)).
Cea mai eficienta metoda este metoda prin care construim o structura de date arborescenta ce ne garanteaza ca orice operatie de tip update sau suma poate fi executata in O(log n). Modul in care construim acest arbore este urmatorul: la radacina avem intervalul [1, n], descendentii acestuia vor fi [1,n/2] si [n/2+1, n]. Vom mentine aceasta maniera recursiva pana cand ajungem la elemente individuale ale array-ului. Dupa construirea arborelui, trecem la operatia de update. Ideea este ca nu dorim sa actualizam toate nodurile, ci doar parintii nodurilor pana cand ajungem la radacina, astfel operatia va fi logaritmica. Pentru suma ideea este similara: noi impartim recursiv intervalul de cautare in jumatati pana cand gasim un nod ce contine intervalul cautat.
In concluzie, arborii de intervale sunt structuri de date arborescente ce permit rezolvarea eficienta a problemelor unde exista update-uri si query-uri pe intervale. Acestia pot fi implementati intr-o multitudine de probleme din concursuri.
Mai jos va las si implementarea mea a arborilor de intervale:

#include <bits/stdc++.h>
using namespace std;
int v[100], a[401];
void build (int st, int dr, int node) {
    if (st == dr) {
        a[node] = v[st];
    }
    else {
        int mij = (st + dr) / 2;
        build (st, mij, node * 2);
        build (mij + 1, dr, node * 2 + 1);
        a[node] = a[ node * 2 ] + a[ node * 2 + 1 ];
    }
}
void update (int st, int dr, int node, int pos, int val) {
    if (st == dr) {
        a[node] = val;
        v[pos] = val;
    }
    else {
        int mij = (st + dr) / 2;
        if (pos <= mij) {
            update (st, mij, node * 2, pos, val);
        }
        else {
            update (mij + 1, dr, node * 2 + 1, pos, val);
        }
        a[node] = a[node * 2 + 1] + a[node * 2];
    }
}
int sum (int st, int dr, int node, int target_st, int target_dr) {
    if (st>target_dr or dr<target_st) {
        return 0;
    }
    else {
        if (target_st <= st and dr <= target_dr) {
            return a[node];
        }
        int mij = (st + dr) / 2;
        return sum (st, mij, node * 2, target_st, target_dr) + sum (mij + 1, dr, node * 2 + 1, target_st, target_dr);
    }
}

Sper ca v-am ajutat!