题解：P13976 数列分块入门 1

zhujianheng · 2025-09-05 22:27:51 · 题解

虽然这题是数列分块题，但是这题也可以用线段树的方案解决，可以发现是单点查询区间更新问题，所以需要懒标记，设 toAdd 表示懒标记，则我们每次在线段树上更新时候，就采用区间三分离的方法，当无贡献的时候就直接返回，当整体贡献的时候这个整体的懒标记都加上 c，否则就在子树中递归，直到整体贡献为止，就实现了一个基本的区间加。

然后如何单点查询，我们单点二选一。如果已经拆分成最小的区间（点），直接返回这个点的懒标记即可。否则二选一：若在左子树内，即当前询问的 id 在左子树的右端点以内，则左子树产生贡献，继续递归并在递归结束以后加上这个点的懒标记，否则右子树产生贡献，同样递归右子树加上这个点的懒标记。其实每次询问一个点，就是某个叶子到根的点权和，而这个叶子就是代表区间 [id,id] 的。

这样一步步模拟实现即可，时间复杂度 O(n \log n) 的。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=500009;
const ll MOD=100000007;
ll n,x[N];
struct Segment{
    ll l,r;
    ll toAdd;
};
Segment tr[N*4];
void build(ll u,ll l,ll r){
    if(l==r){
        tr[u]=(Segment){l,r,x[l]};
        return;
    }
    ll mid=(l+r)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    tr[u]=(Segment){l,r,0};
}
void add(ll u,ll l,ll r,ll delta){
    if(r<tr[u].l||tr[u].r<l) return;
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].toAdd+=delta;
        return;
    }
    add(u*2,l,r,delta);
    add(u*2+1,l,r,delta);
}
ll value(ll u,ll id){
    if(tr[u].l==tr[u].r)
        return tr[u].toAdd;
    if(id<=tr[u*2].r)
        return tr[u].toAdd+value(u*2,id);
    else
        return tr[u].toAdd+value(u*2+1,id);
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++) scanf("%lld",&x[i]); 
    build(1,1,n);
    for(ll i=1;i<=n;i++){
        ll op,l,r,c;
        scanf("%lld %lld %lld %lld",&op,&l,&r,&c);
        if(op==0) add(1,l,r,c);
        else printf("%lld\n",value(1,r));
    }
    return 0;
}