O((n+q)log n) 静态区间异或和

cosf · 2026-09-17 16:47:40 · 休闲·娱乐

O((n + q) \log n) 静态区间异或和

给定一个序列 a_1, \dots, a_n，q 次在线询问，每次给定区间 l, r，求出 \bigoplus_{j=l}^r a_j。其中 \bigoplus 表示将区间内所有数二进制异或起来。

我们可以采用 ST 表求出静态区间异或和。设 b_{i, k} = \bigoplus_{j = i}^{i + 2^k - 1} a_j，这个可以 O(n\log n) 地预处理出来。

假设要询问区间 [l, r] 的异或和。设 k 为最大的满足 2^k \le (r - l + 1) 的正整数。若 2^k = (r - l + 1)，则可以直接返回 b_{l, k}。否则，我们计算 b_{l, k} \oplus b_{r - 2^k + 1, k}，但中间重叠部分异或了两次，需要重新计算。于是我们规约到了子问题 [r - 2^k + 1, l + 2^k - 1]。

可以证明递归的次数为 O(\log n)。设 (r - l + 1) = 2^k + d，则递归一次后区间长度变为 2^k - d。如果 d \ge \frac{1}{3}2^k，则一次递归后区间长度减半。否则 2^k - d \gt 2^{k - 1}，再次递归之后区间长度变为 d。因此两次递归之后区间长度一定会减半，递归次数 \le 2\log_2 n。

于是我们得到了 O(n\log n) - O(\log n) 的静态区间异或和做法，常数是线段树做法的 \frac 12。

这个做法还可以继续扩展，只要任何满足交换律、结合律、自己是自己逆元的信息都可以使用该算法解决。