L’idea di entrambe le strutture dai che hai citato è quella di mantenere dei “rappresentanti”. Per esempio se hai un array di N elementi, con la sqrt decomposition manterrai un altro array di \sqrt N elementi, ognuno dei quali rappresenta una fetta lunga \sqrt N dell’array originale. Con un array lungo 1024, manterrai 32 elementi aggiuntivi (ognuno dei quali si occupa di rappresentare una fetta lunga 32 dell’array originale).
Per fare la ricerca di un singolo elemento, ti basta andarlo a leggere nell’array originale. Per fare la ricerca di un range di elementi, ti basta andare a leggere il valore memorizzato nei rappresentanti che vengono “toccati”. Se il range “si accavalla” su un rappresentante senza includere completamente tutti gli elementi originali da esso rappresentati, allora dovrai andare a leggere manualmente gli elementi di quel rappresentante.
Nota che, nell’esempio dell’array lungo 1024, questo significa (al caso peggiore) andare a leggere 31 elementi originali + 30 rappresentanti + 31 elementi originali. Se questa parte non è chiara, chiedi pure 
Con i segment tree, la storia si complica un po’ perché l’idea dei rappresentanti viene estesa anche ai rappresentanti stessi (la “lista” di rappresentanti ha a sua volta una lista di “super-rappresentanti”, e così via).
In questo vecchio topic puoi trovare alcune risorse utili: