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

目录 前言 例题 特殊应用 总结 前言 在算法竞赛中，维护区间和是个很经典的问题。在数组中，求区间 \([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])\)。 (用队友电脑打的，被他#define int long long了) #include<bits/stdc++.h> #define lowbit(x) ((x)^(-(x))) #define int long long #pragma GCC optimize(2) // #define debug() cout<<"ok"<<endl using namespace std; const int N = 1e5 + 10; const int mod = 2; // const int inf = (int)1e18 + 5; int n; int l,r,i,k; int countxor(int x) { int t = x % 4; switch (t) { case 1: return 1; case 2: return x + 1; case 3: return 0; case 0: return x; } } int countxor1(int up, int x) { if (up >= 4) { int t = x % 4; int xx = k + (x-1)*up; switch (t) { case 1: return xx; case 2: return up; case 3: return xx + up; case 0: return 0; } } else { if (x == 0) return 0; int t = x % 4; int xx = k + (x-1)*up; if (k == 0) { t = (x-1) % 4; switch (t) { case 1: return 2; case 2: return xx + 2; case 3: return 0; case 0: return xx; } } else { switch (t) { case 1: return xx; case 2: return 2; case 3: return xx + 2; case 0: return 0; } } } } int count(int r) { int ans = countxor(r); int len = r + 1; int up = 1ll << i; int cnt = len / up; //计算周期数 len %= up; if (len >= k+1) cnt++; ans ^= countxor1(up,cnt); return ans; } void solve() { cin>>l>>r>>i>>k; if (i == 0) cout << 0 << endl; else cout << (count(r)^count(l-1)) << endl; // cout << count(r) << endl; // cout << count(l-1) << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T = 1; cin >> T; while(T--)solve(); // int sum = 0; // for (int i = 1 ; i <= 1000 ; i += 4) // { // sum ^= i; // cout << i << " " << sum << endl; // } // int sum = 0; // for (int i = 1 ; i <= 1993 ; i++) // { // if (i % 4 == 2) continue; // sum ^= i; // } // cout << sum << endl; return 0; } /* /\_/\ /\_/\ /\_/\ (= q_q) (= u_u) (= o_o) /> \ > /> \ > /> \ > */ CF2026D 题意：给定序列 \(a\)，记 \(s(l,r)\) 表示 \(a\) 在区间 \([l,r]\) 上的和。定义 \(b = [s(1,1),s(1,2),...s(1,n),s(2,2),s(2,3),s(2,n)...s(n,n)]\)，现在有 \(q\) 次询问，每次询问需要返回 \(b\) 在区间 \([l,r]\) 上的和。 观察 \(b\) 序列，它具有类周期的性质。我们将 \([s(1,1)...s(1,n)]\) 记作第 \(1\) 个周期，\([s(2,2)...s(2,n)]\) 记作第 \(2\) 个周期。以此类推。 显然本题也可以转化为前缀和相减。我们现在要考虑 \(b\) 在 \([1,i]\) 上的求和如何处理。 考虑对 \(a\) 中每个元素计算贡献，可以做出表格观察规律： 位置 1 2 3 4 ... n 在第一个周期中出现次数 n n-1 n-2 n-3 ... 1 在第二个周期中出现次数 0 n-1 n-2 n-3 ... 1 在第三个周期中出现次数 0 0 n-2 n-3 ... 1 ...... 注意到每个元素在任何周期中出现的次数都是固定的，因此可以递推维护第 \(i\) 个周期的和。记第 \(i\) 个周期的和为 \(f_i\)。则有： \[f_i = f_{i+1} + (n-i+1) \times a_i \] 若 \(b\) 在 \([1,i]\) 中完整包含了 \(cnt\) 个周期，则这部分答案 \(\sum_{i=1}^{cnt} f_i\) 可以通过预处理 \(f\) 的前缀和快速求出。接下来就是处理最后一个不完整的周期。 现在将最后一个周期当做完整周期来算，考虑减去多算的贡献。 假设这是第 \(1\) 个区间，\(n=4\) 时，我们对比完整区间，列出每个位置多算了几次。 位置 1 2 3 4 [s(1,1)...s(1,3)]中多算次数 1 1 1 1 [s(1,1)...s(1,2)]中多算次数 2 2 2 1 [s(1,1)...s(1,1)]中多算次数 3 3 2 1 [s(1,1)...s(1,0)]中多算次数 4 3 2 1 显然多算的贡献也是有规律的，推广到第 \(i\) 个区间，该区间是 \([s(i,i)...s(i,R)]\)，则多算的贡献是：\(f_{R+1} + (n-R) \times \sum_{j=i}^{R}a_j\)。 到此 \(b\) 在 \([1,i]\) 上的和就彻底推完。答案就是两个前缀和相减。 #include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <cmath> #include <queue> #include <set> #include <map> using namespace std; using ll = long long; typedef pair<int,int> PII; const int N = 3e5 + 10; ll sum[N],f[N]; //原数组前缀和 以i开头周期的和 ll sumf[N]; //f的前缀和 int n; ll count(ll x) { ll cnt; //完整周期数 ll l = 0; ll r = n + 1; while (l+1 != r) { ll mid = (l+r) >> 1; ll num = (2*n-mid+1) * mid / 2; if (num <= x) l = mid; else r = mid; } cnt = l; ll ans = sumf[cnt+1]; x -= (2*n-cnt+1) * cnt / 2; ll R = cnt + x;//不完整周期的右边界 ans -= f[R+1] + (n-R) * (sum[R]-sum[cnt]); //减去多算的贡献 return ans; } void solve() { cin >> n; vector<ll> a(n+10); for (int i = 1 ; i <= n ; i++) { cin >> a[i]; sum[i] = sum[i-1] + a[i]; } for (int i = n ; i >= 1 ; i--) f[i] = f[i+1] + (n-i+1) * a[i]; for (int i = 1 ; i <= n+1 ; i++) sumf[i] = sumf[i-1] + f[i]; int q; cin >> q; while (q--) { ll l,r; cin >> l >> r; cout << count(r) - count(l-1) << endl; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; T = 1; while (T--) solve(); return 0; } 特殊应用 实际上，将区间问题转化为前缀和相减的思想还有更神奇的应用。比如当这个区间只有 \(1\) 个数的时候。 CF2149E 题意：给定一个序列 \(a\) 以及 \(k,l,r\)，计算有多少个区间 \([L,R]\) 满足：区间长度在 \([l,r]\) 之间，并且区间中有恰好 \(k\) 个不同的数。 维护区间恰好有 \(k\) 个不同的数是很困难的，但是我们可以计算有 \(\leq k\) 个不同数的区间个数，这很容易想到通过双指针维护。进一步想，恰有 \(k\) 个不同元素的区间个数，等于有 \(\leq k\) 个不同元素的区间个数 减去 有 \(\leq k-1\) 个不同元素的区间个数。这实际上也是一种前缀和相减。 #include <iostream> #include <vector> #include <map> #define int long long using namespace std; const int N = 2e5 + 10; int a[N]; int n,k,L,R; int count(int x) { map<int,int> mp; int l = 1; int sum = 0; for (int r = 1 ; r <= n ; r++) { mp[a[r]]++; while (r-l+1 > R || mp.size() > x) { mp[a[l]]--; if (mp[a[l]] == 0) mp.erase(a[l]); l++; } sum += max(0ll,r-l-L+2); // cout << l << " " << r << " " << r-l-L+2 << " " << mp.size() << endl; } return sum; } void solve() { cin >> n >> k >> L >> R; for (int i = 1 ; i <= n ; i++) cin >> a[i]; cout << count(k) - count(k-1) << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; while (T--) solve(); return 0; } CF2121F 题意：给定序列 \(a\) 和整数 \(s,x\)，计算有多少个区间，满足区间和等于 \(s\)，且区间最大值等于 \(x\)。 对于区间和，显然有前缀和可以快速查询。但是区间最大值 \(x\) 是并不太好维护的。根据上一题的经验，我们可以计算区间和等于 \(s\)，并且区间最大值 \(\leq x\) 的区间数量。同时计算区间最大值 \(\leq x-1\) 的区间数量。两式相减即为答案。 （不要再写define int long long了，某场比赛因此被卡常了十几发） #include <iostream> #include <vector> #include <map> using namespace std; #define int long long int count(vector<int>& a, vector<int>& sum, int n, int s, int x) { vector<int> vec; vec.push_back(0); for (int i = 1 ; i <= n ; i++) { if (a[i] > x) vec.push_back(i); } vec.push_back(n+1); int ans = 0; for (int i = 0 ; i < vec.size() ; i++) { if (i+1 == vec.size()) continue; int l = vec[i]; int r = vec[i+1]; map<int,int> mp; mp[sum[l]]++; for (int j = l+1 ; j <= r-1 ; j++) { ans += mp[sum[j]-s]; mp[sum[j]]++; } } return ans; } void solve() { int n,s,x; cin >> n >> s >> x; vector<int> a(n+10),sum(n+10); for (int i = 1 ; i <= n ; i++) { cin >> a[i]; sum[i] = sum[i-1] + a[i]; } cout << count(a,sum,n,s,x) - count(a,sum,n,s,x-1) << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; while (T--) solve(); return 0; } 总结 看完上面四道例题，再回头想：为什么要把一个区间问题转化成前缀和相减？ 因为在大部分时候，我们难以甚至根本无法计算出一个区间的贡献。并且对于任意一个区间，我们需要分别讨论左右边界，这是特别容易错的。而计算一个从 \(1\) 开始的前缀和显然更具有普适性。