数列分块入门 1

_H17_ · 2025-09-06 23:51:19 · 题解

题目分析

考虑先差分，相当于给 l,r+1 单点修改，并区间查询，树状数组维护即可。

不知道如何维护？移步我的树状数组题解。

由于被管理员拒绝了，这里把部分我自己题解内容搬运过来。

题目要求我们在较快的时间内实现单点加、区间查询。

如果我们正常做，若干次 [1,n] 的区间查会把时间卡爆。

如果前缀和的话，修改操作需要恢复数组，也很慢。

如果使用差分，查询也要很长时间。

考虑使用树状数组，它的结构大体如下：

我们知道 \operatorname{lowbit}(x) 表示 x 只保留最低的一位 1。

我们让 f_x 的管辖空间是 a_{x-\operatorname{lowbit(x)}+1}\sim a_x。

我们考虑单点修改：对于一个点 x，我们显然知道最小管辖它的是 f_x，之后每次 x\gets x+\operatorname{lowbit}(x)，显然这样子末尾 0 的数量增加了，一定包含。

考虑查询：\sum\limits_{i=l}^{r}a_i=\sum\limits_{i=1}^{r}a_i-\sum\limits_{i=1}^{l-1}a_i。

考虑处理其中一部分：求 1\sim x 的和。

我们考虑到必须要取 x，还不能取更大的，显然 f_x 满足这个条件。

但是 f_x 也包含了 a_{x-\operatorname{lowbit}(x)+1}\sim a_{x-1}，所以我们直接跳树状数组 x\gets x-\operatorname{lowbit}(x)。

时间复杂度：考虑跳 \operatorname{lowbit} 的性质，跳完 \operatorname{lowbit} 之后末尾的 1 又加了一个，至少翻倍，所以修改复杂度是 O(\log n)；查询的复杂度可以考虑为给 x 做二进制拆分（本质就是这样），复杂度也是 O(\log n)。

时间复杂度 O(q\log n)。

双倍经验。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=3e5+2;
int n,q,f[N];
void add(int x,int k){
    #define lowbit(x) ((x)&(-(x)))
    for(;x<=n;x+=lowbit(x))
        f[x]+=k;
    return;
    #undef lowbit
}
int qry(int x){
    #define lowbit(x) ((x)&(-(x)))
    int ret=0;
    for(;x;x-=lowbit(x))
        ret+=f[x];
    return ret;
    #undef lowbit
}
signed main(){
    cin>>n;
    q=n;
    for(int i=1,ai;i<=n;i++){
        cin>>ai;
        add(i,ai),add(i+1,-ai);
    }
    for(int op,l,r,x;q;--q){
        cin>>op>>l>>r>>x;
        if(!op)
            add(l,x),add(r+1,-x);
        else
            cout<<qry(r)<<'\n';
    }
    return 0;
}