Un arbore de intervale este un arbore binar în care fiecărui nod îi este asociat
răspunsul query-ului pentru
un anumit interval (vom numi acest interval "interval de acoperire"). Vom nota cu [Li, Ri] intervalul de acoperire al nodului i. De
asemenea, vom nota cu
tatai părintele nodului i.
Vom atribui rădăcinii intervalul [1,N], iar pentru fiecare nod i diferit de rădăcină vom avea
două cazuri:1.Dacă i este nodul din stânga al tatălui, atunci Li = Ltatai, Ri = (Ltatai + Rtatai)/2. 2.Daca i este nodul din dreapta al tatălui, atunci Li = (Ltatai + Rtatai)/2 + 1, Ri = Rtatai.Observăm că fiecărui nod în afară de rădăcină îi este atribuit un interval de lungime egală cu
jumătate din lungimea intervalului atribuit tatălui său. Astfel, distanța de la rădăcină la orice alt nod este cel
mult log2(N). De asemenea, intervalele de lungime 1 se vor afla mereu în frunze.
În general arborii de intervale se rețin într-un vector.
Pentru ușurință, vom nota cu poznode poziția nodului node în vector.
Arborele fiind binar, pozrad=1 (unde rad este rădăcina arborelui), iar pentru orice alt nod din arbore:
1.Dacă i este nodul din stânga al tatalui, atunci pozi=2*poztatai
2.Daca i este nodul din dreapta al tatalui, atunci pozi=2*poztatai+1.