题解：P13976 数列分块入门 1

a_gold_TomAndJerry · 2025-09-07 19:44:03 · 题解

本题为线段树模版题。

写线段树太过繁琐，这里用树状数组实现。

注意，因为 c 的范围高达 2^{63}，所以要开long long。

AC Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
int n;
ll a[maxn],tree[maxn];
int lowbit(int x){
    return x&-x;
}
void add(int p,ll v){
    for(;p<=n;p+=lowbit(p)) tree[p]+=v;
}
void add_range(int l,int r,ll x){
    add(l,x);
    if(r+1<=n) add(r+1,-x);
} 
ll query(int p){
    ll res=0;
    for(;p;p-=lowbit(p)) res+=tree[p];
    return res;
}
int main(){
    scanf("%d",&n);
    a[0]=0;
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        add(i,a[i]-a[i-1]);
    }
    for(int i=1;i<=n;++i){
        int op,l,r;
        ll c;
        scanf("%d%d%d%lld",&op,&l,&r,&c);
        if(op==0) add_range(l,r,c);
        else cout<<query(r)<<'\n';
    }
    return 0;
}