如何将区间问题巧妙转化为前缀和相减技巧？

目录 前言 例题 特殊应用 总结 前言 在算法竞赛中，维护区间和是个很经典的问题。在数组中，求区间 \([l,r]\) 的和 \(sum[l,r]\) 显然可以用前缀和来优化。那么，这个思想能不能推广呢？比如现在有一个函数 \(f\)，需要求 \(\sum_{i=l}^r f(i)\)，显然这个式子也可以转化为 \(sum[1,r] - sum[1,l-1]\)。 为什么要做这步转化呢？假设 \(f\) 是个周期函数，那么直接求 \(sum[l,r]\) 可能会面临左右边界都不满一个周期的情况，需要进行很多边界讨论。而显然此时 \(sum[1,i]\) 是更好求的，因为我们只需要对右边界讨论。又比如 \(f\) 是个从 \(1\) 开始有规律的函数，此时 \(sum[1,i]\) 显然也很好求。 例题 CF2036F 题意：给定 \(l,r,i,k\)，求区间 \([l,r]\) 上所有满足 \(x≢k (mod\ 2^i)\) 的 \(x\) 的异或和。 区间异或和显然也可以通过前缀异或和转化：\(XOR[l,r] = XOR[1,r] ⊕ XOR[1,l-1]\)。 本题有个前置知识：记 \(f(i)\) 为 从 \(1\) 到 \(i\) 的异或和，则 \(f\) 以 \(4\) 为周期存在规律。 \[f(x) = \begin{cases} 1, & x≡1 (mod \ 4) \\ x+1, & x≡2 (mod \ 4) \\ 0, & x≡3 (mod \ 4) \\ x, & x≡0 (mod \ 4) \end{cases} \] 只是求 \(XOR[l,r]\) 是简单的，难点在于处理 \(mod \ 2^i = k\) 的数。记 \([l,r]\) 上所有 \(x≢k (mod\ 2^i)\) 的 \(x\) 的异或和为 \(XOR1[l,r]\)。我们实际上就是求 \(XOR[l,r] ⊕ XOR1[l,r]\)。 那么我们能快速求出 \(XOR1[1,x]\) 吗？答案是可以。因为 \(XOR[1,x]\) 存在以 \(4\) 为周期的规律。所以 \(XOR1[1,x]\) 必然也呈现周期性的规律。这个规律可以通过打表得到。由于 \(1、2\) 是唯二 \(\leq 4\) 的幂次，所以这两种情况需要特判。 记 \(f_{1}(x)\) 为前 \(x\) 个 \(mod\ 2^i = k\) 的数的异或和。(注意这个函数的定义，\(x\) 表示前 \(x\) 个符合条件的数的数目) 令 \(xx = k + (x-1)2^i\) 当 \(i = 1\) : 若 \(k = 0\)， \[f1(x) = \begin{cases} 2, & x≡1 (mod \ 4) \\ xx+2, & x≡2 (mod \ 4) \\ 0, & x≡3 (mod \ 4) \\ xx, & x≡0 (mod \ 4) \end{cases} \] 若\(k = 1\)， \[f1(x) = \begin{cases} xx, & x≡1 (mod \ 4) \\ 2, & x≡2 (mod \ 4) \\ xx+2, & x≡3 (mod \ 4) \\ 0, & x≡0 (mod \ 4) \end{cases} \] 当 \(i \ge 2\) 时： \[f1(x) = \begin{cases} xx, & x≡1 (mod \ 4) \\ 2^i, & x≡2 (mod \ 4) \\ xx+2^i, & x≡3 (mod \ 4) \\ 0, & x≡0 (mod \ 4) \end{cases} \] 一切都处理完之后，本题答案显而易见：\((XOR[1,r] ⊕ XOR1[1,r]) ⊕ (XOR[1,l-1] ⊕ XOR1[1,l-1])\)。