\(i\) 番目のクエリと \(i+1\) 番目のクエリが \(X_i \neq X_{i+1}\) を満たすとき、\(2\) つのクエリの順番を入れ替えても最終的な答えは変わりません。

このことを確かめるには、 まず \(X_i = 0, X_{i+1} = 1\) かつ \(Y_i = 0, Y_{i+1} = 0\) としても一般性を失いません。 さらに、この \(2\) つのクエリでは、\(A\) の \(4\) つの要素 \(A_{4k}, A_{4k+1}, A_{4k+2}, A_{4k+3}\) 同士での加算が各 \(k = 0, 1, 2, \ldots, 2^{N-2}-1\) について”並列”に行われるので、特に代表として \(k = 0\) についてのみ確かめれば十分です、 そこで、\((A_0, A_1, A_2, A_3)\) に対して実際に操作を行うことで、その結果が \(2\) つのクエリの実行順序によらないことが確かめられます。

したがって、\(X_i\) が等しいクエリ同士の相対順序は損なわないようにクエリの順番を並べ替え、

• まず、\(X_i = 0\) であるクエリのみをすべて実行し、
• 次に、\(X_i = 1\) であるクエリのみをすべて実行し、
• 次に、\(X_i = 2\) であるクエリのみをすべて実行し、
• \(\cdots\)
• 最後に、\(X_i = N-1\)であるクエリのみをすべて実行する

としても良いので、結局、すべてのクエリの \(X_i\) が等しい場合の問題を十分高速に解ければ良いです。

一般性を失わず \(X_1 = X_2 = \cdots = X_Q = 0\) とします。 また、\(i\) 個目までのクエリを実行した直後の \(A\) を \(A^{(i)} = (A^{(i)}_0, A^{(i)}_1, \ldots, A^{(i)}_{2^N-1})\) と表します。

\[ \mathbf{M}_0 := \left[\begin{matrix} 1 & 0 \\ 1 & 1\\ \end{matrix}\right], \,\,\, \mathbf{M}_1 := \left[\begin{matrix} 1 & 1 \\ 0 & 1\\ \end{matrix}\right] \]

とすると、

任意の \(k = 0, 1, 2, \ldots, 2^{N-1}\) について、

\[ \left[\begin{matrix} A^{(i)}_{2k}\\ A^{(i)}_{2k+1}\\ \end{matrix}\right] = \mathbf{M}_{Y_i} \left[\begin{matrix} A^{(i-1)}_{2k}\\ A^{(i-1)}_{2k+1}\\ \end{matrix}\right] \]

であるので、任意の \(k = 0, 1, 2, \ldots, 2^{N-1}\) について、

\[ \left[\begin{matrix} A^{(Q)}_{2k}\\ A^{(Q)}_{2k+1}\\ \end{matrix}\right] = \mathbf{M}_{Y_Q}\mathbf{M}_{Y_{Q-1}}\ldots \mathbf{M}_{Y_1} \left[\begin{matrix} A^{(0)}_{2k}\\ A^{(0)}_{2k+1}\\ \end{matrix}\right] \]

です。よって、\(Q\) 個の行列の積 \(\mathbf{M}_{Y_Q}\mathbf{M}_{Y_{Q-1}}\ldots \mathbf{M}_{Y_1}\) を一度計算しておけば、それを用いて \(A^{(Q)}\) の全要素を、各要素あたり \(\mathrm{O}(1)\) 時間で計算できます。