526互联

暑假集训随笔2 主席树/二维树状数组

发布时间 2023-07-19 20:59:31作者: wxk123

P4514 上帝造题的七分钟

题意

维护对二维平面上的矩形区域各元素进行加法以及对矩形区域求和
链接：https://www.luogu.com.cn/problem/P4514

思路

通过二维树状数组维护的二维前缀和利用差分实现矩形区域的区间加法与区间求和。
具体而言，二维的前缀和可以仿照一维的前缀和进行定义
一维的前缀和与差分数组的关系为

\[ \sum_{i=1}^{n}a[i]=sum[n]\qquad d[i]=a[i]-a[i-1] \]

相应地可以定义二维前缀和与差分

\[ \sum_{i=1}^{n}\sum_{j=1}^{m}a[i][j]=sum[n][m]\qquad d[n][m]=a[n][m]-a[n-1][m]-a[n][m-1]+a[n-1][m-1] \]

有了差分数组，我们可以仿照一维下的树状数组维护区间加减和求和的方式去维护二维情况。
对于一维下的情况，我们知道公式\(\sum_\limits{i=1}^{n}\sum_\limits{j=1}^{i}d[i]\)通过寻找\(d[i]\)被计算的次数
可以转化为\(\sum_\limits{i=1}^{n}(n-i+1)*d[i]\),于是可以通过多维护一个根据下表加权意义下的树状数组来解决这一计算问题。
对于二维情况，这一方法仍然适用。
image
通过以上例子我们可以得到对下方公式计算的启发.

\[\sum_{i=1}^x\sum_{j=1}^y\sum_{h=1}^i\sum_{k=1}^jd[h][k] \]

容易发现，第i行的元素在遍历到\([i,n]\)时才会被计算，
对于列也有类似的结论。故其可转化为

\[\sum_{i=1}^x\sum_{j=1}^yd[i][j]\times(x-i+1)\times(y-j+1) \]

\[=\begin{aligned}\sum_{i=1}^x\sum_{j=1}^yd[i][j]\times(xy+x+y+1)-d[i][j]\times i(y+1)-d[i][j]\times j(x+1)+d[i][j]\times i\times j\end{aligned} \]

其中x和y是定值，只需维护对应的四个树状数组即可。

代码

代码的细节不多，但是需要对二维树状数组有比较深刻的理解，比如我就在写update的时候搞错了更新要乘的i和j应该与循环变量相同还是和函数参数相同。实际上这个问题并不困难，因为我们本质上是单点修改因此数组各个位置的更新量自然应该是对应修改位置的定值。

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define dnt double
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define dow(i,j,k) for(int i=(j);i>=(k);--i)
#define pr pair
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
inline int read(int &x) {
   x=0;int ff=1;char ch=getchar();
   while (ch<'0'||ch>'9') {
   	if (ch=='-') ff=-1;ch=getchar();
   }
   while (ch>='0'&&ch<='9') {
   	x=x*10+ch-48;ch=getchar();
   }
   return x*ff;
}
void write(int x) {
 if (x > 9)write(x / 10);
 putchar((x % 10) + '0');
}
inline int max(int a,int b) {return a>b?a:b;}
inline int min(int a,int b) {return a>b?b:a;}
inline int exgcd(int a,int b,int&x,int&y) {
   if(b==0) {x=1,y=0 ;return a ;} 
   else {int r=exgcd(b,a%b,x,y);int t=x ;x=y ;y=t-a/b*y ;return r ;}
}
const int N=2050;
int n,m;
int	f[N][N],fj[N][N],fi[N][N],fij[N][N];
int lowbit(int x){
   return x&(-x);
}
void update(int x,int y,int val){
   for(int i=x;i<=n;i+=lowbit(i)){
   	for(int j=y;j<=m;j+=lowbit(j)){
   		f[i][j]+=val;
   		fj[i][j]+=y*val;//j*val
   		fi[i][j]+=x*val;//
   		fij[i][j]+=x*y*val;//
   	}
   }
}
int query(int x,int y){
   int anss=0,anssi=0,anssj=0,anssij=0;
   for(int i=x;i>0;i-=lowbit(i)){
   	for(int j=y;j>0;j-=lowbit(j)){
   		anss+=f[i][j];
   		anssi+=fi[i][j];
   		anssj+=fj[i][j];
   		anssij+=fij[i][j]; 
   	}
   }
   return anss*(x*y+x+y+1)-anssi*(y+1)-anssj*(x+1)+anssij;
}
signed main() {
//	ios::sync_with_stdio(false),cin.tie(NULL);
   char s;int x1,y1,x2,y2,del;
   cin>>s>>n>>m;
   //cout<<n<<" "<<m<<endl;
   while((cin>>s)){
   //cout<<s<<endl;
   	if(s=='L'){
   		cin>>x2>>y2>>x1>>y1>>del;
   		update(x1+1,y1+1,del);
   		update(x2,y2,del);
   		update(x1+1,y2,-del);
   		update(x2,y1+1,-del);	
   	}
   	else{
   		cin>>x2>>y2>>x1>>y1;
   		cout<<query(x1,y1)-query(x2-1,y1)-query(x1,y2-1)+query(x2-1,y2-1)<<endl;
   	}
   }
   
   return 0;
}