Corte em √n pedaços

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.

Fig. 1 — Soma de intervalo com decomposição em √nconsulta de 10% a 90% do vetor

Carregando a figura interativa…

Versão estática: com n = 1.000.000, somar 80% do vetor custa 800.000 passos no laço simples e 2.798 com blocos de 1.000.

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.