题解：P13976 数列分块入门 1

guoshengyu1231 · 2025-09-07 09:44:02 · 题解

提供一种不用打懒标记的分块写法。

思路

题目要求维护一个序列，并支持区间修改和单点查询的操作，乍一看这题不打懒标记似乎根本没法做，但实际上只需要进行一些小处理，就能将其转化为一般的区间维护问题。\\

我们发现，虽然区间修改操作是一个非常棘手的问题，但单点查询简单到就连基本的数组都能完成，那我们怎样才能均摊时间复杂度呢？众所周知，用差分的方法可以实现 O(1) 时间复杂度进行区间修改，但相对的，要想求单点的值，就需要计算整个前缀和，但如果我们对原先的差分数组进行分块维护，那问题不就变成单点修改和区间查询了吗？\\

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e5+5;
const int maxm=710;
int n,m,a[maxn];
int L[maxm],R[maxm],tot,len,in[maxn],sum[maxm];
//L[]:每块的左边界，R[]:每块的右边界，tot：块数，len：块长，in[]:每个位置对应的块编号，sum[]:每块的和
int op,x,y,k;
void init()
{
    tot=len=sqrt(n);//计算块长和块数
    if(len*len<n) tot++;
    for(int i=1;i<=tot;i++)
     {
        R[i]=i*len;
        L[i]=R[i-1]+1;
     }
    R[tot]=n;//确定每块边界
    for(int i=1;i<=tot;i++)
     for(int j=L[i];j<=R[i];j++)
      {
        in[j]=i;
        sum[i]+=a[j];
      }
}
void add(int x,int k)//单点修改
{
    a[x]+=k;sum[in[x]]+=k;
}
int query(int l,int r)//区间查询
{
    int p=in[l],q=in[r];
    int ans=0;
    if(p==q)
     {
        for(int i=l;i<=r;i++) ans+=a[i];
        return ans;
     }
    for(int i=l;i<=R[p];i++) ans+=a[i];
    for(int i=p+1;i<=q-1;i++) ans+=sum[i];
    for(int i=L[q];i<=r;i++) ans+=a[i];
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i;i--) a[i]-=a[i-1];//差分处理
    init();
    for(int i=1;i<=n;i++)
     {
        cin>>op;
        if(op==0)
         {
            cin>>x>>y>>k;
            add(x,k);add(y+1,-k);//差分操作
         } 
        else 
         {
            cin>>x>>y>>k;
            cout<<query(1,y)<<"\n";//等价于求前缀和
         }
     }
    return 0;
}