Java教程

LibreOJ 131 树状数组2：区间修改，单点查询

本文主要是介绍LibreOJ 131 树状数组2：区间修改，单点查询，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目地址

Solution

前面已经知道了树状数组的单点修改和区间查询。这里利用差分的思想：具体来说，维护 \(b\) 数组：

\[b[i] = a[i]-a[i-1] \]

其中 \(a\) 为原来数组。可以发现

\[a[i] = \sum_{k=1}^ib[k] \]

因此我们只需要对 \(b\) 利用树状数组维护，get_sum[i]即可得到原来数组单点的值。而对于区间更新，我们只需要在两个端点 \(l,r\) 打上标记即可：

\[update(l,x);update(r+1,-x) \]

点击查看代码 
int n,q;
const int N = 1e6+5;
ll a[N], b[N];
ll c[N];

ll lowbit(int x){return x&(-x);}

void update(int i, ll k){
    // add k on i-th position
    while(i<=N){
        c[i]+=ll(k); i+= lowbit(i);
    }
}
ll get_sum(int i){
    // get sum from 1-i
    ll ans = 0;
    while(i>0){
        ans+=ll(c[i]);i-=lowbit(i);
    }
    return ans;
}

int main(){
    //ios::sync_with_stdio(false);
    n = read();q = read();
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        b[i] = a[i]-a[i-1];
        update(i,b[i]);
    }
    while(q--){
        int tmp = read();
        if(tmp==1){
            int l=read(),r = read();
            ll x;scanf("%lld",&x);
            update(l,x);update(r+1,-x);
        }
        else{
            int pos = read();
            cout<<get_sum(pos)<<endl;
        }
    }
    
}
这篇关于LibreOJ 131 树状数组2：区间修改，单点查询的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航