蓝桥杯备赛 Day15 树形数据结构

树状数组基础

解决问题

1.树状数组可以解决“动态修改动态查询区间和”的问题(前缀和是多次修改完多次查询)，不过一般解决单点修改+区间查询问题
2.树状数组先要了解lowbit操作，这是一种二进制操作，取一个数字二进制表达中最低位的1以及后面所有的0，例如:
lowbit(4)=lowbit(100)=100=4
lowbit(6)=lowbit(110)=10=2
lowbit函数代码:

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

3.树状数组即一个数组int t[N]，表示为$$t[i]=\sum _{j=i-lowbit(i)+1}^{i}a[i]$$
即维护一个长为lowbit(x)的[x-lowbit[x]+1,x]的区间和
4.单点修改函数,如下图，修改a[3]+k,就是t[3]+k,t[4]+k,t[8]+k,而3+lowbit(3)=4,4+lowbit(4)=8,直到小于等于n

//给a[k]增加x
void update(int k,int x){for(int i=k;i<=n;i+=lowbit(i)){t[i]+=x;}
}

5.区间查询函数:如下图，查询区间[3,7],即获得[1,7]-[1,2],而[1,7]=t[7]+t[6]+t[4],而7-lowbit(7)=6,6-lowbit(6)=4，直到为0(不能等于0，不然死循环，所以树状数组开始不能为0)

//获取[1,k]的区间和
void getprefix(int k){int res=0;for(int i=k;i>0;i-=lowbit(i)){res+=t[i];}return res;
}

![[树状数组.png]]

殷老师排队

学习:
(1)记得输入a[i]的时候**update(i,a[i])初始化t数组**
(2)单点修改不仅要调用update函数，还有记得修改a[i]数组
代码:

#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;
int a[N],t[N],n,m;int lowbit(int x){return x & (-x);
}//第x个学生的魅力值增加k 
void update(int x,int k){for(int i=x;i<=n;i+=lowbit(i)){t[i]+=k;}
} //获取[1,x]的学生的魅力值和
int getprefix(int x){int res=0;for(int i=x;i>0;i-=lowbit(i)){res+=t[i];}return res;
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];update(i,a[i]); //初始化t数组 }for(int i=1;i<=m;i++){int op;cin>>op;if(op==1){int x,z;cin>>x>>z;	update(x,z-a[x]);a[x]=z; //记得更新a[x] }else{int x;cin>>x;cout<<(2*x-n)*a[x]+getprefix(n)-2*getprefix(x)<<endl;}}return 0;
}

拼十字

学习:
(1)此题暴力筛选会超时，充要条件是矩形 1 的长度严格大于矩形 2 的长度并且矩形 1 的宽度严格小于矩形 2 的宽度，就可以给结构体矩形首先按长度降序排列(如果长度一样则按宽度降序排列，保证不会选这两个),然后问题就转化为求宽度小于当前矩形的宽度的矩形数量和,就可以以宽度为索引id，a[i]表示宽度为i的矩形数量，输入一个矩形就是单点增加a[i]+1,查询就是[1,宽度i-1]的数量前缀和，单点修改+区间查询可以用动态数组解决
(2)而三种颜色就是三个树状数组，用类来解决
(3)类构造初始化列表:

Tree(ll size):t(size+1,0){}	

等价于:

Tree(ll size){t.resize(size+1,0);}

代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
int n;
ll ans;class Tree{private:vector<ll> t;public:Tree(ll size):t(size+1,0){}	// 使用初始化列表//Tree(ll size){t.resize(size+1,0);}// 使用 resize 初始化int lowbit(int x){return x & (-x);} //宽度x的数量++ void update(int x){for(int i=x;i<=N;i+=lowbit(i)){ //宽度最大到N,不是n t[i]++;}}//返回[1,x]的和ll get(int x){ll res=0;for(int i=x;i>0;i-=lowbit(i)){res+=t[i];}return res;} 
};struct Rec{int l,w,c;
}r[N];bool cmp(Rec &r1,Rec &r2){if(r1.l!=r2.l)	return r1.l>r2.l; //降序排列，树状数组即求小于当前宽度的矩形个数即可//相等则按宽度降序排列，保证不会考虑到return r1.w>r2.w; 
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>r[i].l>>r[i].w>>r[i].c;}sort(r+1,r+n+1,cmp);//初始化三个颜色的树状数组 Tree T_R(N); //宽度为索引 Tree T_Y(N);Tree T_B(N);for(int i=1;i<=n;i++){if(r[i].c==0){ans= (ans+T_Y.get(r[i].w-1)+T_B.get(r[i].w-1))%mod;T_R.update(r[i].w);}else if(r[i].c==1){ans= (ans+T_R.get(r[i].w-1)+T_B.get(r[i].w-1))%mod;T_Y.update(r[i].w);}else{ans= (ans+T_R.get(r[i].w-1)+T_Y.get(r[i].w-1))%mod;T_B.update(r[i].w);}}cout<<ans;return 0;
}