我们可以将莫队算法从一维扩展到更高维度。
考虑正在维护 $k$ 维结构的信息，且每一维的大小分别为 $n_1,n_2,\cdots,n_k$。为了下文叙述方便，我们将维度大小序列复制一份，得到 $n_{k+1},\cdots,n_{2k}\quad(n_i=n_{i-k})$。我们同时维护 $2k$ 个指针，第 $i\ \ (i\leq k)$ 个指针维护第 $i$ 维左端点，第 $i\ \ (k<i\leq 2k)$ 个指针维护第 $i-k$ 维右端点。按询问处理顺序依次移动到每个询问对应的位置上。 （更多…）