# Corte em √n pedaços

> A primeira palestra que dei, no primeiro Code Camp IFPB/ACM, foi sobre isso.

- Autor: Marcello Oliveira (https://mrcll.me/about/)
- Publicado: 30 de out. de 2026
- Temas: ICPC, Fundamentos
- URL: https://mrcll.me/pt/stories/root-decomposition/

A primeira palestra que dei foi no primeiro Code Camp IFPB/ACM, sobre uma técnica que cabe numa frase: divida o vetor em blocos de tamanho √n e guarde a soma de cada bloco.

É isso. Uma consulta de soma num intervalo, no loop simples, custa até n passos. Com blocos, custa as pontas soltas, no máximo 2√n elementos nas bordas, mais os blocos inteiros do meio, no máximo √n somas que você já tem. Atualizar um valor é corrigir um elemento e a soma de um bloco.

> Figura interativa (SqrtDecomp): use a versão web em https://mrcll.me/pt/stories/root-decomposition/

Para 800.000 elementos, é a diferença entre 800.000 passos e 2.798. Por que √n e não outro tamanho? Blocos maiores dão menos blocos e pontas mais longas; blocos menores, o contrário. √n é onde os dois custos se encontram.

Não é a estrutura mais rápida que existe; uma segment tree faz melhor. Mas a decomposição em raiz é a que você escreve certo em dez minutos, numa maratona, sob pressão, e isso conta muito. A estrutura boa o bastante que você entende por inteiro ganha da ótima que você copia.