Hash de Prefixo, Seleção em Três Partes e o Algoritmo de Mo

O Artigo 15 tratou bits como conjuntos. Este artigo fecha o capítulo dos arrays com três técnicas que respondem a perguntas sobre trechos de um vetor sem examinar cada trecho por inteiro.

A primeira é o hash de prefixo, que aplica a ideia das somas de prefixo do Artigo 13 a cadeias de caracteres. Cada trecho vira um número, e comparar dois trechos custa uma comparação de inteiros. O preço é a probabilidade de dois trechos diferentes produzirem o mesmo número, e boa parte deste artigo trata de como manter essa probabilidade desprezível contra uma entrada escrita por um adversário. A segunda técnica é a partição em três partes, a bandeira holandesa de Dijkstra, que completa a seleção do Artigo 10 quando o vetor tem muitos valores repetidos. A terceira é o algoritmo de Mo, que responde a consultas de intervalo fora de linha reordenando-as para que uma janela ande pouco.

As medições foram feitas com o MSVC do Visual Studio 18.10.3, com /std:c++latest /O2, em um Intel Core i7-10750H. Cada tempo é a mediana de cinco execuções depois de uma de aquecimento, salvo onde o texto disser outra coisa. Os programas deste artigo, com as entradas e as saídas esperadas de cada caso de teste, estão em serie-blog/competitiva-16.

1. O hash de prefixo

Uma cadeia $s=s_0{s}_1\dots s_{n-1}$ pode ser lida como os coeficientes de um polinômio em uma base $B$, calculado módulo um inteiro $M$:

$$h(s)=s_0{B}^{n-1}+s_1{B}^{n-2}+\cdots +s_{n-1}(\mathrm{mod}M).$$