• 日期: 2026-03-14
  • 标签: 程序员

目录

前言

在算法竞赛中，维护区间和是个很经典的问题。在数组中，求区间 \([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
#define lowbit(x) ((x)^(-(x)))
#define int long long 
#pragma GCC optimize(2)
// #define debug() cout<<"ok"<= 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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

using ll = long long;
typedef pair 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 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 
#include 
#include 
#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 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 
#include 
#include 
using namespace std;

#define int long long

int count(vector& a, vector& sum, int n, int s, int x)
{
    vector 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 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 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\) 开始的前缀和显然更具有普适性。


原文地址: https://www.cveoy.top/t/topic/qF9O 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录