Uma árvore de segmentos permite manter, para cada intervalo, quantos valores 1
existem nele.

Na construção inicial, cada folha guarda o valor do elemento correspondente do
vetor. Cada vértice interno guarda a soma dos dois filhos, ou seja, a quantidade
de valores 1 no intervalo representado por esse vértice.

Para inverter uma posição $i$, alteramos a folha correspondente de 0 para 1 ou
de 1 para 0. Em seguida, recalculamos as somas no caminho da folha até a raiz.
Essa operação custa $O(\log N)$.

Para encontrar o $k$-ésimo valor 1, descemos pela árvore a partir da raiz. Seja
$L$ a quantidade de valores 1 no filho esquerdo:

\begin{itemize}
    \item se $L > k$, então o $k$-ésimo 1 está no filho esquerdo;
    \item caso contrário, ele está no filho direito, e passamos a procurar o
    $(k-L)$-ésimo 1 dentro desse filho.
\end{itemize}

Quando chegamos a uma folha, seu índice é a resposta da consulta. A busca também
custa $O(\log N)$.

Assim, a complexidade total é $O((N+M)\log N)$ em tempo e $O(N)$ em memória.