算法竞赛小trick：将区间问题转化为前缀和相减

目录

• 前言
  
• 例题
  
• 特殊应用
  
• 总结
  

前言

在算法竞赛中，维护区间和是个很经典的问题。在数组中，求区间 \([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了)

1. #include#define lowbit(x) ((x)^(-(x)))#define int long long #pragma GCC optimize(2)// #define debug() cout>r>>i>>k;    if (i == 0) cout  l >> r;        cout  a[i];    cout  T;    while (T--) solve();    return 0;}

复制代码

CF2121F
题意：给定序列 \(a\) 和整数 \(s,x\)，计算有多少个区间，满足区间和等于 \(s\)，且区间最大值等于 \(x\)。
对于区间和，显然有前缀和可以快速查询。但是区间最大值 \(x\) 是并不太好维护的。根据上一题的经验，我们可以计算区间和等于 \(s\)，并且区间最大值 \(\leq x\) 的区间数量。同时计算区间最大值 \(\leq x-1\) 的区间数量。两式相减即为答案。
（不要再写define int long long了，某场比赛因此被卡常了十几发）

1. #include #include #include using namespace std;#define int long longint count(vector& a, vector& sum, int n, int s, int x){    vector vec;    vec.push_back(0);    for (int i = 1 ; 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 mp;        mp[sum[l]]++;        for (int j = l+1 ; j > n >> s >> x;    vector a(n+10),sum(n+10);    for (int i = 1 ; i > a[i];        sum[i] = sum[i-1] + a[i];    }    cout  T;    while (T--) solve();    return 0;}

复制代码

总结

看完上面四道例题，再回头想：为什么要把一个区间问题转化成前缀和相减？
因为在大部分时候，我们难以甚至根本无法计算出一个区间的贡献。并且对于任意一个区间，我们需要分别讨论左右边界，这是特别容易错的。而计算一个从 \(1\) 开始的前缀和显然更具有普适性。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！