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

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

区间修改区间查询

题目链接：YbtOJ

---

解题思路

我们可以把区间修改区间查询的差分与单点修改区间查询结合起来，也就是二维树状数组维护二维前缀和再加上差分。

code

#include<iostream>
#include<cstdio>
#define lb(x) (x&(-x))
#define int long long
using namespace std;int n,m,p;
int a,b,c,d,x;
int tree[2050][2050][5];void in(int x,int y,int z)
{for(int i=x;i<=n;i+=lb(i))for(int j=y;j<=m;j+=lb(j)){tree[i][j][1]+=z;tree[i][j][2]+=z*x;tree[i][j][3]+=z*y;tree[i][j][4]+=z*x*y;}
}int fd(int x,int y)
{int s=0;for(int i=x;i;i-=lb(i))for(int j=y;j;j-=lb(j))s+=tree[i][j][1]*(x+1)*(y+1)-tree[i][j][2]*(y+1)-tree[i][j][3]*(x+1)+tree[i][j][4];return s;
}signed main()
{cin>>n>>m;while(scanf("%lld",&p)!=EOF){scanf("%lld%lld%lld%lld",&a,&b,&c,&d);if(p==1){scanf("%lld",&x);in(c+1,d+1,x);in(c+1,b,-x);in(a,d+1,-x);in(a,b,x);}elsecout<<fd(c,d)-fd(c,b-1)-fd(a-1,d)+fd(a-1,b-1)<<endl;}
}

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

---