【ybt】【数据结构 树状数组 课过 例4】区间修改区间查询

本文主要是介绍【ybt】【数据结构 树状数组 课过 例4】区间修改区间查询，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

区间修改区间查询

题目链接：YbtOJ

---

解题思路

区间操作，我们可以想到差分。
设差分数组为 $d$ ，那么求 $\sum _{i=1}^n{a}_i$ 就可以转换为 $\sum _{i=1}^n\sum _{j=1}^i{d}_i$ 。
暴力枚举是 $O(n^2)$ 的，我们考虑优化。
我们可以发现：$d_1$ 出现了 $n$ 次，$d_2$ 出现了 $n-1$ 次，$d_i$ 出现了 $n-i+1$ 次，所以$\sum _{i=1}^n{a}_i=\sum _{i=1}^n(d_i\ast (n+1)-d_i\ast i)$，我们用树状数组维护 $d_i$ 和 $d_i\ast i$ 即可。

code

#include<iostream>
#include<cstdio>
#define lb(x) (x&(-x))
#define int long long
using namespace std;int n,q;
int c[1000010];
int c1[1000010];void in(int x,int y)
{for(int i=x;i<=n;i+=lb(i))c[i]+=y,c1[i]+=x*y;
}int fd(int x)
{int s=0;for(int i=x;i;i-=lb(i))s+=c[i]*(x+1)-c1[i];return s;
}signed main()
{cin>>n>>q;for(int i=1;i<=n;i++){int t;scanf("%lld",&t);in(i,t);in(i+1,-t);}while(q--){int t,l,r;scanf("%lld%lld%lld",&t,&l,&r);if(t==1){int x;scanf("%lld",&x);in(l,x);in(r+1,-x);}elsecout<<fd(r)-fd(l-1)<<endl;}
}

这篇关于【ybt】【数据结构 树状数组 课过 例4】区间修改区间查询的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---