差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:树套树 [2020/07/11 17:16]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:树套树 [2020/07/30 14:23] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-====== 树套树 1 ======
+====== 树套树 ======
+===== 树状数组套树状数组 =====
+==== 简介 ====
+一般用与维护二维矩阵，码量以及常数小，通常涉及差分。
+==== 模板题 ====
+[[https://www.luogu.com.cn/problem/P4514|洛谷p4514]]
+维护一个矩阵，支持以下操作：
+  - 将以 $(r_1,c_1),(r_2,c_2)$ 为顶点的矩阵内全部元素加上 $k$
+  - 输出 $(r_1,c_1),(r_2,c_2)$ 为顶点的矩阵内全部元素的和
+考虑二维差分，设矩阵元素 $a_{x,y}=\sum_{i=1}^x\sum_{j=1}^y b_{i,j}$，则
+\begin{equation}S_{i,j}=\sum_{x=1}^r\sum_{y=1}^c a_{x,y}=\sum_{x=1}^r\sum_{y=1}^c\sum_{i=1}^x\sum_{j=1}^y b_{i,j}=\sum_{i=1}^r\sum_{j=1}^c (r-i+1)(c-j+1)b_{i,j}\end{equation}
+展开得
+\begin{equation}S_{i,j}=(r+1)(c+1)\sum_{i=1}^r\sum_{j=1}^c b_{i,j}-(c+1)\sum_{i=1}^r\sum_{j=1}^c ib_{i,j}-(r+1)\sum_{i=1}^r\sum_{j=1}^c jb_{i,j}+\sum_{i=1}^r\sum_{j=1}^c ijb_{i,j}\end{equation}
+考虑分别维护以下四项
+\begin{equation}\sum_{i=1}^r\sum_{j=1}^c b_{i,j},\sum_{i=1}^r\sum_{j=1}^c ib_{i,j},\sum_{i=1}^r\sum_{j=1}^c jb_{i,j},\sum_{i=1}^r\sum_{j=1}^c ijb_{i,j}\end{equation}
+修改操作变为 $b_{r_1,c_1}+=v,b_{r_2+1,c_1}-=v,b_{r_1,c_2+1}-=v,b_{r_2+1,c_2+1}+=v$。
+查询操作变为 $S=S_{r_2,c_2}-S_{r_1-1,c_2}-S_{r_2,c_1-1}+S_{r_1-1,c_1-1}$。
+空间复杂度 $O(n^2)$，时间复杂度 $O(q\log^2 n)$。
+<hidden 查看代码>
+<code cpp>
+#define lowbit(x) (x)&(-x)
+const int MAXN=2050;
+struct BIT{
+	int a[4][MAXN][MAXN],n,m;
+	void modify(int r,int c,int v){
+		for(int i=r;i<=n;i+=lowbit(i)){
+			for(int j=c;j<=m;j+=lowbit(j)){
+				a[0][i][j]+=v;
+				a[1][i][j]+=v*r;
+				a[2][i][j]+=v*c;
+				a[3][i][j]+=v*r*c;
+			}
+		}
+	}
+	void add(int r1,int c1,int r2,int c2,int v){
+		modify(r1,c1,v);modify(r2+1,c1,-v);
+		modify(r1,c2+1,-v);modify(r2+1,c2+1,v);
+	}
+	int pre_sum(int r,int c){
+		int ans[4]={0};
+		for(int i=r;i;i-=lowbit(i)){
+			for(int j=c;j;j-=lowbit(j)){
+				_for(k,0,4)
+				ans[k]+=a[k][i][j];
+			}
+		}
+		return ans[0]*(r+1)*(c+1)-ans[1]*(c+1)-ans[2]*(r+1)+ans[3];
+	}
+	int query(int r1,int c1,int r2,int c2){
+		return pre_sum(r2,c2)-pre_sum(r1-1,c2)-pre_sum(r2,c1-1)+pre_sum(r1-1,c1-1);
+	}
+}tree;
+char order[1000];
+int main()
+{
+	scanf("X %d %d\n",&tree.n,&tree.m);
+	int a,b,c,d,v;
+	while(~scanf("%s",order)){
+		if(order[0]=='L'){
+			a=read_int(),b=read_int(),c=read_int(),d=read_int(),v=read_int();
+			tree.add(a,b,c,d,v);
+		}
+		else{
+			a=read_int(),b=read_int(),c=read_int(),d=read_int();
+			enter(tree.query(a,b,c,d));
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 线段树套线段树 =====
+==== 简介 ====
+一般用于解决树状数组套树状数组无法解决的二维偏序问题，通常涉及权值线段树、动态开点等。
+==== 模板题 ====
+[[https://www.luogu.com.cn/problem/P3332|洛谷p3332]]
+维护 $n$ 个可重集，支持以下操作：
+  - 将 $c$ 加入编号为 $[l\sim r]$ 的集合
+  - 查询编号为 $[l\sim r]$ 的集合的并集中第 $c$ 大的元素
+考虑权值线段树套线段树，第一维维护每个数值，第二维维护每个集合在某个数值区间拥有的元素个数。
+为防止爆内存，第二维线段树需要动态开点，同时考虑线段树标记永久化优化常数。
+时空间复杂度均为 $O(q\log v\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=(5e4+5)*4,MAXM=40;
+struct Node{
+	int ch[2],tag;
+	LL sz;
+}node[MAXN*MAXM];
+int lef[MAXN],rig[MAXN],root[MAXN],n,tot;
+void build_2D(int k,int L,int R){
+	lef[k]=L,rig[k]=R;
+	if(L==R)
+	return;
+	int M=L+R>>1;
+	build_2D(k<<1,L,M);
+	build_2D(k<<1|1,M+1,R);
+}
+void update_1D(int &k,int lef,int rig,int L,int R){
+	if(!k)k=++tot;
+	if(L<=lef&&rig<=R)
+	return node[k].sz+=rig-lef+1,node[k].tag++,void();
+	int mid=lef+rig>>1;
+	if(mid>=L)
+	update_1D(node[k].ch[0],lef,mid,L,R);
+	if(mid<R)
+	update_1D(node[k].ch[1],mid+1,rig,L,R);
+	node[k].sz=node[node[k].ch[0]].sz+node[node[k].ch[1]].sz+1LL*(rig-lef+1)*node[k].tag;
+}
+void update_2D(int L,int R,int v){
+	int k=1,mid;
+	while(lef[k]<rig[k]){
+		update_1D(root[k],1,n,L,R);
+		mid=lef[k]+rig[k]>>1;
+		k<<=1;
+		k|=(mid<v);
+	}
+	update_1D(root[k],1,n,L,R);
+}
+LL query_1D(int k,int lef,int rig,int L,int R,int tag){
+	if(!k)
+	return 1LL*(min(rig,R)-max(lef,L)+1)*tag;
+	if(L<=lef&&rig<=R)
+	return node[k].sz+1LL*(rig-lef+1)*tag;
+	int mid=lef+rig>>1;
+	if(mid>=R)
+	return query_1D(node[k].ch[0],lef,mid,L,R,tag+node[k].tag);
+	else if(mid<L)
+	return query_1D(node[k].ch[1],mid+1,rig,L,R,tag+node[k].tag);
+	else
+	return query_1D(node[k].ch[0],lef,mid,L,R,tag+node[k].tag)+query_1D(node[k].ch[1],mid+1,rig,L,R,tag+node[k].tag);
+}
+int query_2D(int L,int R,LL rk){
+	int k=1;LL trk;
+	rk--;
+	while(lef[k]<rig[k]){
+		trk=query_1D(root[k<<1|1],1,n,L,R,0);
+		k<<=1;
+		if(trk<=rk)
+		rk-=trk;
+		else
+		k|=1;
+	}
+	return lef[k];
+}
+int main()
+{
+	n=read_int();
+	build_2D(1,1,n);
+	int q=read_int(),opt,l,r;
+	LL c;
+	while(q--){
+		opt=read_int(),l=read_int(),r=read_int(),c=read_LL();
+		if(opt&1)
+		update_2D(l,r,c);
+		else
+		enter(query_2D(l,r,c));
+	}
+    return 0;
+}
+</code>
+</hidden>
 ===== 线段树/树状数组套名次树 =====
@@ 行 26: / 行 213: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-    int t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline LL read_LL(){
-    LL t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline char get_char(){
-    char c=getchar();
-    while(c==' '||c=='\n'||c=='\r')c=getchar();
-    return c;
-}
-inline void write(LL x){
-    register char c[21],len=0;
-    if(!x)return putchar('0'),void();
-    if(x<0)x=-x,putchar('-');
-    while(x)c[++len]=x%10,x/=10;
-    while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=(5e4+5)*4,MAXS=MAXN*20,Inf=0x7fffffff;
 template <typename T>
@@ 行 285: / 行 425: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-    int t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline LL read_LL(){
-    LL t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline char get_char(){
-    char c=getchar();
-    while(c==' '||c=='\n'||c=='\r')c=getchar();
-    return c;
-}
-inline void write(LL x){
-    register char c[21],len=0;
-    if(!x)return putchar('0'),void();
-    if(x<0)x=-x,putchar('-');
-    while(x)c[++len]=x%10,x/=10;
-    while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=5e4+5,MAXS=MAXN*20,Inf=0x7fffffff;
 template <typename T>
@@ 行 548: / 行 641: @@
 </hidden>
-=== 动态开点权值线段树套名次树版本 ===
+=== 权值线段树套名次树版本 ===
 转换一下思路，考虑外层维护权值，内层维护位置。那么 $\text{rank}$ 操作查询 $0\sim v-1$ 区间的满足条件的点的个数。
@@ 行 558: / 行 651: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-    int t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline LL read_LL(){
-    LL t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline char get_char(){
-    char c=getchar();
-    while(c==' '||c=='\n'||c=='\r')c=getchar();
-    return c;
-}
-inline void write(LL x){
-    register char c[21],len=0;
-    if(!x)return putchar('0'),void();
-    if(x<0)x=-x,putchar('-');
-    while(x)c[++len]=x%10,x/=10;
-    while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=5e4+5,MAXS=MAXN*40,Inf=0x7fffffff;
 template <typename T>
@@ 行 841: / 行 887: @@
 	}
     return 0;
+}
+</code>
+</hidden>
+===== 树状数组套权值线段树 =====
+==== 简介 ====
+功能类似线段树/树状数组套名次树。
+其实权值线段树和名次树在功能上有许多相同点，权值线段树码量相对较少，但空间复杂度多一个 $O(\log v)$。
+==== 模板题 ====
+[[https://www.luogu.com.cn/problem/P3759|洛谷p3759]]
+该题等价于维护一个数组，支持一下操作：
+  - 修改某个点的点权
+  - 询问满足位置在 $[l_1,r_1]$ 且权值在 $[l_2,r_2]$ 范围内的点个数和点权和。
+树状数组的每个节点的权值线段树维护区间 $[x-\text{lowbit}(x)+1,x]$ 的权值分布，每个权值记录点个数和点权和。
+空间复杂度 $O(n\log n\log v)$，单次操作时间复杂度 $O(\log n\log v)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e4+5,MAXM=400,mod=1e9+7;
+struct Node{
+	int ch[2],sz,sum;
+}node[MAXN*MAXM];
+struct Ans{
+	int sz,sum;
+	Ans operator + (const Ans &b){
+		Ans c;
+		c.sz=sz+b.sz;
+		c.sum=sum+b.sum;
+		if(c.sum>=mod)c.sum-=mod;
+		return c;
+	}
+	Ans operator - (const Ans &b){
+		Ans c;
+		c.sz=sz-b.sz;
+		c.sum=sum-b.sum;
+		if(c.sum<0)c.sum+=mod;
+		return c;
+	}
+	void operator += (const Ans &b){
+		sz+=b.sz;
+		sum+=b.sum;
+		if(sum>=mod)sum-=mod;
+	}
+	void operator -= (const Ans &b){
+		sz-=b.sz;
+		sum-=b.sum;
+		if(sum<0)sum+=mod;
+	}
+	Ans(int sz=0,int sum=0):sz(sz),sum(sum){}
+};
+#define lowbit(x) (x)&(-x)
+int n,root[MAXN],tot;
+int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
+void add(int pos,int v){
+	while(pos<=n){
+		c[pos]+=v;
+		if(c[pos]>=mod)
+		c[pos]-=mod;
+		d[pos]++;
+		pos+=lowbit(pos);
+	}
+}
+Ans sum(int pos){
+	int s1=0,s2=0;
+	while(pos){
+		s2+=c[pos];
+		if(s2>=mod)
+		s2-=mod;
+		s1+=d[pos];
+		pos-=lowbit(pos);
+	}
+	return Ans(s1,s2);
+}
+void update_1D(int &k,int lef,int rig,int pos,int v1,int v2){
+	if(!k)k=++tot;
+	node[k].sz+=v2,node[k].sum=(node[k].sum+v1)%mod;
+	if(lef==rig)
+	return;
+	int mid=lef+rig>>1;
+	if(mid>=pos)
+	update_1D(node[k].ch[0],lef,mid,pos,v1,v2);
+	else
+	update_1D(node[k].ch[1],mid+1,rig,pos,v1,v2);
+}
+void update_2D(int k,int pos,int v1,int v2){
+	while(k<=n){
+		update_1D(root[k],1,n,pos,v1,v2);
+		k+=lowbit(k);
+	}
+}
+Ans query_1D(int k,int lef,int rig,int L,int R){
+	if(!k)
+	return Ans(0,0);
+	if(L<=lef&&rig<=R)
+	return Ans(node[k].sz,node[k].sum);
+	int mid=lef+rig>>1;
+	if(mid>=R)
+	return query_1D(node[k].ch[0],lef,mid,L,R);
+	else if(mid<L)
+	return query_1D(node[k].ch[1],mid+1,rig,L,R);
+	return query_1D(node[k].ch[0],lef,mid,L,R)+query_1D(node[k].ch[1],mid+1,rig,L,R);
+}
+Ans query_2D(int L,int R,int ql,int qr){
+	if(ql>qr)
+	return Ans(0,0);
+	int pos1=L-1,pos2=R;
+	Ans re=Ans(0,0);
+	while(pos1){
+		re-=query_1D(root[pos1],1,n,ql,qr);
+		pos1-=lowbit(pos1);
+	}
+	while(pos2){
+		re+=query_1D(root[pos2],1,n,ql,qr);
+		pos2-=lowbit(pos2);
+	}
+	return re;
+}
+int main()
+{
+	n=read_int();
+	int q=read_int(),lef,rig;
+	LL ans=0;Ans temp;
+	_rep(i,1,n)
+	a[i]=read_int(),b[i]=read_int();
+	for(int i=n;i;i--){
+		add(a[i],b[i]);
+		temp=sum(a[i]-1);
+		ans=(ans+temp.sum+1LL*b[i]*temp.sz)%mod;
+		update_2D(i,a[i],b[i],1);
+	}
+	while(q--){
+		lef=read_int();
+		rig=read_int();
+		if(lef==rig){
+			enter(ans);
+			continue;
+		}
+		if(lef>rig)
+		swap(lef,rig);
+		temp=query_2D(lef+1,rig-1,a[lef]+1,n)-query_2D(lef+1,rig-1,1,a[lef]-1);
+		ans=(ans+temp.sum+1LL*b[lef]*temp.sz)%mod;
+		temp=query_2D(lef+1,rig-1,1,a[rig]-1)-query_2D(lef+1,rig-1,a[rig]+1,n);
+		ans=(ans+temp.sum+1LL*b[rig]*temp.sz)%mod;
+		if(a[lef]<a[rig])
+		ans=(ans+b[lef]+b[rig])%mod;
+		else
+		ans=(ans-b[lef]-b[rig])%mod;
+		enter((ans+mod)%mod);
+		update_2D(lef,a[lef],-b[lef],-1);update_2D(rig,a[rig],-b[rig],-1);
+		swap(a[lef],a[rig]);swap(b[lef],b[rig]);
+		update_2D(lef,a[lef],b[lef],1);update_2D(rig,a[rig],b[rig],1);
+	}
+	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具