Uma árvore de segmentos guarda um resumo de cada bloco de posições: as folhas têm valores individuais e cada pai combina seus dois filhos. Serve qualquer operação associativa com elemento neutro, como a soma com 0, o mínimo com infinito, o máximo ou o MDC com 0. Uma pergunta sobre um intervalo combina então O(log n) blocos, e uma atualização pontual recalcula um único caminho, de uma folha até a raiz.
A versão de baixo para cima cabe em poucas linhas: folhas de n a 2n - 1 e pai i = combinar(2i, 2i + 1). Use-a quando uma árvore de Fenwick não bastar, porque a operação não pode ser desfeita por subtração (mínimo, máximo, MDC) ou porque você precisa buscar dentro da árvore, como a primeira posição cujo valor é pelo menos x.
Quando as atualizações cobrem intervalos inteiros, acrescente propagação preguiçosa: um nó coberto por uma atualização anota a mudança e só a repassa aos filhos quando alguém precisa deles. Em uma entrevista, diga primeiro a função de combinação e seu elemento neutro, e depois o custo de atualizar e de consultar.
Uma atualização pontual recalcula um caminho da folha até a raiz.