数据结构
设计数据结构¶
例题¶
- set+优先队列，比较复杂
- 1825. 求出 MK 平均值
- 有序数组加队列
- 1606. 找到处理最多请求的服务器
- 715. Range 模块
- 380. O(1) 时间插入、删除和获取随机元素
- 659. 分割数组为连续子序列
- 哈希表+优先队列
并查集¶
模板¶
vector<int>parents;
vector<int>h;
void initiate(int n)
{
parents=vector<int>(n,0);
h=vector<int>(n,1);
for(int i=0;i<n;i++)
parents[i]=i;
}
int find(int target)
{
if(target!=parents[target])
parents[target]=find(parents[target]);
return parents[target];
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return;
if(h[x]<=h[y])
{
h[y]+=h[x];
parents[x]=parents[y];
}
else
{
h[x]+=h[y];
parents[y]=parents[x];
}
}
class UF:
def __init__(self, N):
self.p = list[range(N)]
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, x, y):
if x == y:
return
x = self.find(x)
y = self.find(y)
if x != y:
self.p[x] = self.p[y]
带权并查集¶
-
带权并查集的核心能力就是维护多个元素之间的连通以及偏移关系，甚至可以维护多个偏移关系。而偏移量可以理解为当前结点到根结点的距离之和。
-
按秩合并统计了每个联通快的元素数目，本质上也是一种带权并查集
-
以路径长度作为权值，维护压缩前后的权值
const int N = 200010;
int s[N]; //集
int d[N]; //权值：记录当前结点到根结点的距离
int ans;
void init_set(){ //初始化
for(int i = 0; i <= N; i++) { s[i] = i; d[i] = 0; }
}
int find_set(int x){ //带权值的路径压缩
if(x != s[x]) {
int t = s[x]; //记录父结点
s[x] = find_set(s[x]); //路径压缩。递归最后返回的是根结点
d[x] += d[t]; //权值更新为x到根结点的权值
}
return s[x];
}
void merge_set(int a, int b,int v){ //合并
int roota = find_set(a), rootb = find_set(b);
if(roota == rootb){
if(d[a] - d[b] != v) ans++;
}
else{
s[roota] = rootb; //合并
d[roota] = d[b]- d[a] + v;
}
}
-
d 表示的是从根节点到一个节点的距离，由于 find 路径压缩之后直接连接到了根节点，确实了原先父节点的那一段权值，因此要加上
-
难点在于在路径压缩中维护正确的权值
- 跟不同时的等式关系 relation(roota,rootb)=d[b]-d[a]+relation
-
根相同时的等式关系 d[a]-d[b]==relation
- 结合排序优化
- 1632. 矩阵转换后的秩
- hdu 3038(带权并查集)
- P1196银河英雄传说(带权并查集)
种类并查集¶
-
普通并查集智能表示朋友的朋友是朋友，种类并查集还可以表示敌人的敌人是朋友
-
种类并查集根据要维护的关系的种类数目需要比普通并查集开几倍大的空间，并且也需要进行相应次数的union
- 将仇恨关系从小到大排序，直到哪一个不在能分散到两个监狱里为止，这就是可以实现的最小仇恨值
- 开二倍大小[1,n]用于维护朋友关系（即两个囚犯位于同一个监狱），[n+1,2n]维护敌人关系（一个人的敌人必须位于个一各监狱），当仇恨双方位于同一个并查集时就说明不能再继续分散了
for(int i=1;i<=m;++i){
int fa = find(x[i].a);//a的同一个监狱集合
int fb = find(x[i].b);//b的同一个监狱集合
int ffa = find(x[i].a + n);//a的另一个监狱集合
int ffb = find(x[i].b + n);//b的另一个监狱集合
if(fa == fb ){//如果当前在同一个监狱，会引发冲突，输出。
printf("%d\n",x[i].val);
return 0;
}
bin[fa] = ffb;//a就在b的另一个监狱中
bin[fb] = ffa;//b就在a的另一个监狱中
}
- P2024食物链(带权并查集/种类并查集)
- 更为复杂，要维护三种关系：同类，吃，被吃。因此要开三倍空间并查集
- 划分为三组ABC，对每一个关系都假设在任意一个发生
if (opt == 1) {
if (find(u + n) == find(v) || find(u) == find(v + n)) { ans++; }
else {
fa[find(u)] = find(v);
fa[find(u + n)] = find(v + n);
fa[find(u + n + n)] = find(v + n + n);
}
} else {
if (find(u) == find(v) || find(u) == find(v + n)) { ans++; }
else {
fa[find(u + n)] = find(v);
fa[find(u + n + n)] = find(v + n);
fa[find(u)] = find(v + n + n);
}
}
树状数组¶
- 可以解决大部分基于区间上的更新以及求和问题。
-
标准版解决的是单点更新，区间查询的问题
-
动态（元素可变）求解前（后）缀问题
- 操作复杂度
log(n) - 数组大小n
-
-
lowbit函数
- x&-x：获取x最后一个1所代表的大小
- 如1010返回2，1100返回4
- C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i]; //k为i的二进制中从最低位到高位连续零的长度
-
如：
- C[1] = A[1];
- C[2] = A[1] + A[2];
- C[3] = A[3];
- C[4] = A[1] + A[2] + A[3] + A[4];
- C[5] = A[5];
- C[6] = A[5] + A[6];
- C[7] = A[7];
- C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];
-
2k=lowbit
-
SUMi = C[i] + C[i-2k1] + C[(i - 2k1) - 2k2] + .....；
- 初始化：
- 初始化树状数组全部元素为零
- 对每一位逐个按照原数组的值update
离散化¶
- 用于处理较大的数据范围
- 可以使用set排序进行重新映射
单点更新、区间查询¶
- 要注意的是对树状数组的初始化（如根据a对c进行初始化，也必须通过update函数来进行，不应该直接修改c的值）
int n;
int a[1005],c[1005]; //对应原数组和树状数组(树状数组大小与原数组一致，要求下标从1开始)
int lowbit(int x){
return x&(-x);
}
void update(int i,int k){ //在i位置加上k（是变化量）
while(i <= n){
c[i] += k;
i += lowbit(i);
}
}
int getsum(int i){ //求A[1 - i]的和
int res = 0;
while(i > 0){
res += c[i];
i -= lowbit(i);
}
return res;
}
扩展-区间更新（差分）¶
区间更新，单点查询¶
-
引入差分建树
-
框架不变，只不过才操作时采用差分
-
c++ int main(){ 25 cin>>n; 27 for(int i = 1; i <= n; i++){ 28 cin>>a[i]; 29 updata(i,a[i] - a[i-1]); //输入初值的时候，也相当于更新了值 31 } 32 33 //[x,y]区间内加上k 34 updata(x,k); //A[x] - A[x-1]增加k 35 updata(y+1,-k); //A[y+1] - A[y]减少k 36 37 //查询i位置的值 38 int sum = getsum(i); 39 40 return 0; 41 }
区间更新，区间查询¶
-
仅仅使用普通的前缀和只能实现单点查询，维护更多的前缀和组合出范围值。
-
-
-
维护两个数状数组，sum1[i] = D[i]，sum2[i] = D[i]*(i-1);在利用查分范围修改的同时实现范围查询
int n,m;
int a[50005] = {0};
int sum1[50005]; //(D[1] + D[2] + ... + D[n])
int sum2[50005]; //(1*D[1] + 2*D[2] + ... + n*D[n])
int lowbit(int x){
return x&(-x);
}
void updata(int i,int k){
int x = i; //因为x不变，所以得先保存i值
while(i <= n){
sum1[i] += k;
sum2[i] += k * (x-1);
i += lowbit(i);
}
}
int getsum(int i){ //求前缀和
int res = 0, x = i;
while(i > 0){
res += x * sum1[i] - sum2[i];
i -= lowbit(i);
}
return res;
}
int main(){
cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i];
updata(i,a[i] - a[i-1]); //输入初值的时候，也相当于更新了值
}
//[x,y]区间内加上k
updata(x,k); //A[x] - A[x-1]增加k
updata(y+1,-k); //A[y+1] - A[y]减少k
//求[x,y]区间和
int sum = getsum(y) - getsum(x-1);
return 0;
}
二维区间修改区间查询¶
- 时间复杂度为\(log(nm)\)
- 使用差分实现范围修改，维护额外的值实现范围查询
//修改比较简单，修改为二重循环
void update(int x,int y,int d){
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j)){
t1[i][j] += d; t2[i][j] += x*d;
t3[i][j] += y*d; t4[i][j] += x*y*d;
}
}
- 记差分数组D和原数组a，即\(a[c][d]=\sum^c_{i=1}\sum^d_{j=1}D[i][j]\)
- 查询就是\(\(\sum^c_{i=a}\sum^d_{j=b}a[i][j]=\sum^c_{i=1}\sum^d_{j=1}a[i][j]- \\ \sum^c_{i=1}\sum^{b-1}_{j=1}a[i][j]-\sum^{a-1}_{i=1}\sum^d_{j=1}a[i][j]+\sum^{a-1}_{i=1}\sum^{b-1}_{j=1}a[i][j]\)\)
-
```c++ #include
using namespace std; const int N = 2050; int t1[N][N],t2[N][N],t3[N][N],t4[N][N]; #define lowbit(x) ((x) & - (x))
int n,m; void update(int x,int y,int d){ for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)){ t1[i][j] += d; t2[i][j] += xd; t3[i][j] += yd; t4[i][j] += xyd; } } int sum(int x,int y){ int ans = 0; for(int i=x;i>0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j)) ans += (x+1)(y+1)t1[i][j] - (y+1)t2[i][j] - (x+1)t3[i][j] + t4[i][j]; return ans; } int main(){ char ch[2]; scanf("%s",ch); scanf("%d%d",&n,&m);
while(scanf("%s",ch)!=EOF){ int a,b,c,d,delta; scanf("%d%d%d%d",&a,&b,&c,&d); if(ch[0]=='L'){ scanf("%d",&delta); update(a, b, delta); update(c+1,d+1, delta); update(a, d+1,-delta); update(c+1,b, -delta); } else printf("%d\n",sum(c,d)+sum(a-1,b-1)-sum(a-1,d)-sum(c,b-1)); }
return 0; }
```
- 需要维护4个树状数组
偏序问题¶
-
与归并排序的渐进时间复杂相同
-
典：离散化树状数组，统计一个数组中每一个元素前面或后面更大（更小）元素的数目
-
即查询动态数组内定范围内的整数数目
-
-
```c++ const int N = 500010; int tree[N],rank[N],n; //注：rank是C++的保留字，如果加了using namespace std，编译通不过 //在需要用c++定义的函数和变量时，例如sort，这样写：std::sort() struct point{ int num,val;}a[N]; bool cmp(point x,point y){ if(x.val == y.val) return x.num < y.num; //如果相等，让先出现的更小 return x.val < y.val; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i].val); a[i].num = i; //记录顺序，用于离散化 } sort(a+1,a+1+n,cmp); //排序 for(int i=1;i<=n;i++) rank[a[i].num]=i; //离散化，得到新的数字序列rank[]
long long ans=0; /for(int i=1;i<=n;i++){ //正序处理 update(rank[i],1); ans += i-sum(rank[i]); }/ for(int i=n;i>0;--i){ //倒序处理 update(rank[i],1); ans += sum(rank[i]-1); } printf("%lld",ans); return 0; }
```
区间最值¶
-
单点修改区间最值
-
单步操作复杂度\((logn)^2\)
-
c++ void update(int x,int value){//修改x位置为value while(x<=n){ tree[x]=value; for(int i=1;i<lowbit(x);i<<=1) tree[x]=max(tree[x],tree[x-i]); x+=lowbit(x); } }//与常规的树状数组不同，除了向下传递还要向下检查 //查询也比较复杂，因为区间最值并不具有前缀性质 int query(int L,int R){//返回区间最大值 int ans=0; while(L<=R){ ans=max(ans,a[R]); R--; while(R-L>=lowbit(R)){ ans=max(ans,tree[R]); R-=lowbit(R); } } return ans; }
种类数目问题¶
-
离线查询，按照右区间对查询排序，逐渐更新num数组，一个元素只有最后一次出现的位置才被赋值为1，前缀和就是种类数
-
c++ for(int i=0;i<m;i++){ for(int j=last+1;j<=query[i].second;j++){ if(check.find(arr[j])==check.end()){ check[arr[j]]=j; updata(j,1); } else{ //不是第一次出现要先把之前计数的减去 updata(check[arr[j]],-1); check[arr[j]]=j; updata(j,1); } } }
例题¶
-
二维转化为一维
-
- 寻找前面更小元素与后面更小元素
-
- 二维(x,y)<(_x,_y)，对一维排序，另一维度使用树状数组处理
-
-
把要查找的元素也插入到set中，用set排序生成映射实现离散化
-
```c++ class Solution { public: int countRangeSum(vector
& nums, int lower, int upper) { long long sum = 0; vector preSum = {0};//前缀和 for (int v: nums) { sum += v; preSum.push_back(sum); } set<long long> allNumbers; for (long long x: preSum) {//妙 allNumbers.insert(x); allNumbers.insert(x - lower); allNumbers.insert(x - upper); } // 利用哈希表进行离散化 unordered_map<long long, int> values; int idx = 0; for (long long x: allNumbers) { values[x] = idx; idx++; } int ret = 0; BIT bit(values.size()); for (int i = 0; i < preSum.size(); i++) { int left = values[preSum[i] - upper], right = values[preSum[i] - lower]; ret += bit.query(right + 1) - bit.query(left); bit.update(values[preSum[i]] + 1); } return ret;} }; ```
-
线段树¶
- 线段树详解
- 动态求解区间问题，比树状数组更为强大
- 操作复杂度
log(n) 
-
除了最后一层外都是满的
-
将一个区间划分为[left,mid][mid+1,right]
-
一般来说使用静态数组实现二叉树结构，开四倍元素数目数组
- l = fa*2 （左子树下标为父亲下标的两倍）
- r = fa*2+1（右子树下标为父亲下标的两倍+1）
- 要求下标从1开始
- 下标从0开始则为fa*2+1和fa*2+2
模板¶
- 区间修改&区间查询
- lazy-tag：修改区间时先只通过打标记的方式对区间进行整体上的修改，当线段区间的一致性被破坏之后再把变化的值向下传递。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
ll a[N]; //记录数列的元素，从a[1]开始
ll tree[N<<2]; //tree[i]：第i个结点的值，表示一个线段区间的值，例如最值、区间和
ll tag[N<<2]; //tag[i]：第i个结点的lazy-tag，统一记录这个区间的修改
ll ls(ll p){ return p<<1; } //定位左儿子：p*2
ll rs(ll p){ return p<<1|1;} //定位右儿子：p*2 + 1
void push_up(ll p){ //从下往上传递区间值
tree[p] = tree[ls(p)] + tree[rs(p)];
//本题是区间和。如果求最小值，改为：tree[p] = min(tree[ls(p)], tree[rs(p)]);
}//参数中的pl,pr表示节点对应的线段范围
void build(ll p,ll pl,ll pr){ //建树。p是结点编号，它指向区间[pl, pr]
tag[p] = 0; //lazy-tag标记
if(pl==pr){tree[p]=a[pl]; return;} //最底层的叶子，赋值
ll mid = (pl+pr) >> 1; //分治：折半
build(ls(p),pl,mid); //左儿子
build(rs(p),mid+1,pr); //右儿子
push_up(p); //从下往上传递区间值
}
void addtag(ll p,ll pl,ll pr,ll d){ //给结点p打tag标记，并更新tree
tag[p] += d; //打上tag标记
//限制更新父节点，对子树懒更新
tree[p] += d*(pr-pl+1); //计算新的tree
}
void push_down(ll p,ll pl,ll pr){ //不能覆盖时，把tag传给子树
if(tag[p]){ //有tag标记，这是以前做区间修改时留下的
ll mid = (pl+pr)>>1;
addtag(ls(p),pl,mid,tag[p]); //把tag标记传给左子树
addtag(rs(p),mid+1,pr,tag[p]); //把tag标记传给右子树
tag[p]=0; //p自己的tag被传走了，归0
}
}
void update(ll L,ll R,ll p,ll pl,ll pr,ll d){ //区间修改：把[L, R]内每个元素加上d，p为当前节点，plpr为其子树范围
if(L<=pl && pr<=R){ //完全覆盖，直接返回这个结点，它的子树不用再深入了
addtag(p, pl, pr,d); //给结点p打tag标记，下一次区间修改到p时会用到
return;
}
push_down(p,pl,pr); //如果不能覆盖，把tag传给子树（如果需要的话）
ll mid=(pl+pr)>>1;
if(L<=mid) update(L,R,ls(p),pl,mid,d); //递归左子树
if(R>mid) update(L,R,rs(p),mid+1,pr,d); //递归右子树
push_up(p); //更新（下层更新了，上层要保证最新）
}
ll query(ll L,ll R,ll p,ll pl,ll pr){
//查询区间[L,R]；p是当前结点（线段）的编号，[pl,pr]是结点p表示的线段区间
if(pl>=L && R >= pr) return tree[p]; //完全覆盖，直接返回
push_down(p,pl,pr); //不能覆盖，递归子树（要先pushdown保证子树的值为真实值）
ll res=0;
ll mid = (pl+pr)>>1;
if(L<=mid) res+=query(L,R,ls(p),pl,mid); //左子结点有重叠
if(R>mid) res+=query(L,R,rs(p),mid+1,pr); //右子结点有重叠
return res;
}
int main(){
ll n, m; scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n); //建树
while(m--){
ll q,L,R,d; scanf("%lld",&q);
if (q==1){ //区间修改：把[L,R]的每个元素加上d
scanf("%lld%lld%lld",&L,&R,&d);
update(L,R,1,1,n,d);
}
else { //区间询问：[L,R]的区间和
scanf("%lld%lld",&L,&R);
printf("%lld\n",query(L,R,1,1,n));
}
}
return 0;
}
应用¶
特殊操作¶
- 对区间进行开方操作并计算区间和
- 由于在数据范围内开方7次就会变成0，因此每次操作对非1的部分开方是可以接受的（判断一个子树是否全1，全1则停止进一步计算）
- 多种修改操作和幂查询
- 加乘赋值，查询和平方立方
- 打3种标记
- change使得add和multi失效
- multi使得add*multi
- down时按照change->multi->add
- 平方与立方和维护三个sum数组
- (a+c)2=a2+c2+2ac：sum2[new]=sum2[old]+(R-L+1)c2+2sum1[old]*c
- (a+c)3=a3+c3+3c(a2+ac)：sum3[new]=sum3[old]+(R-L+1)c3+3c(sum2[old]+sum1[old]*c)
- 二分操作
- 通过二分确定第一个使得区间满足某种条件的元素位置（对查询范围进行二分枚举即可）
- 离散化
区间最值（区间min替换）吉如一线段树¶
-
对于只是要求最值得问题只需要维护min/max值即可
-
进行操作：将[L,R]内 ai替换为min(ai,x)
-
query支持获取区间最大值以及区间和，需要将最值操作与区间和联系起来
-
使用4个tag：区间和sum、区间最大值ma、严格次大值se、最大值个数num
-
更新
-
ma<=x：无需修改
-
se<x<ma：修改只影响最大值，sum-=num(ma-x)，ma=x
-
se>=x无法直接修改，递归左右子
-
这么做是为了减少向下push的次数，se起到了类似剪枝的作用
-
c++ #include<bits/stdc++.h> using namespace std; #define ll long long const int N = 1e6 + 10; ll sum[N<<2], ma[N<<2], se[N<<2], num[N<<2]; //num:区间的最大值个数 ll ls(ll p){ return p<<1; } ll rs(ll p){ return p<<1|1;} void pushup(int p) { //从下往上传递 sum[p] = sum[ls(p)] + sum[rs(p)]; //传递区间和 ma[p] = max(ma[ls(p)], ma[rs(p)]); //传递区间最大值 if (ma[ls(p)] == ma[rs(p)]) { //对tag进行更新 se[p] = max(se[ls(p)], se[rs(p)]); num[p] = num[ls(p)] + num[rs(p)]; } else { se[p] = max(se[ls(p)],se[rs(p)]); se[p] = max(se[p],min(ma[ls(p)], ma[rs(p)])); num[p] = ma[ls(p)] > ma[rs(p)] ? num[ls(p)] : num[rs(p)]; } } void build(int p, int pl, int pr) { if (pl == pr) { //叶子 scanf("%lld", &sum[p]); ma[p] = sum[p]; se[p] = -1; num[p] = 1; return; } ll mid = (pl+pr) >> 1; build(ls(p),pl,mid); build(rs(p),mid+1,pr); pushup(p); } void addtag(int p, int x) { if (x >= ma[p]) return; sum[p] -= num[p] * (ma[p] - x); ma[p] = x; } void pushdown(int p) { addtag(ls(p), ma[p]); //把标记传给左子树 addtag(rs(p), ma[p]); //把标记传给左子树 } void update(int L, int R, int p, int pl, int pr, int x) { if (x >= ma[p]) return; //情况（1） if (L<=pl && pr<=R && se[p] < x) { addtag(p, x); return;} //情况（2） //情况（3） pushdown(p); ll mid = (pl+pr) >> 1; if (L<=mid) update(L, R, ls(p), pl, mid, x); if (R>mid) update(L, R, rs(p), mid+1, pr, x); pushup(p); } int queryMax(int L, int R, int p, int pl, int pr) { if (pl>=L && R >= pr) return ma[p]; pushdown(p); int res = 0; ll mid = (pl+pr) >> 1; if (L<=mid) res = queryMax(L, R, ls(p), pl, mid); if (R>mid) res = max(res, queryMax(L, R, rs(p), mid+1, pr)); return res; } ll querySum(int L, int R, int p, int pl, int pr) { if (L <= pl && R >= pr) return sum[p]; pushdown(p); ll res = 0; ll mid = (pl+pr) >> 1; if (L<=mid) res += querySum(L, R, ls(p), pl, mid); if (R>mid) res += querySum(L, R, rs(p), mid+1, pr); return res; } int main(){ int T; scanf("%d", &T); while (T--) { int n,m; scanf("%d%d", &n, &m); build(1, 1, n); while (m--) { int q, L, R, x; scanf("%d%d%d", &q, &L, &R); if (q == 0){ scanf("%d", &x); update(L, R, 1, 1, n, x);} if (q == 1) printf("%d\n", queryMax(L, R, 1, 1, n)); if (q == 2) printf("%lld\n", querySum(L, R, 1, 1, n)); } } return 0; }
区间合并¶
连续元素数目¶
-
初始时数组全部为1，可以对数组进行单点修改（0/1），查询占据下表x的全为1的子数组的长度
-
维护区间前缀1（pre）和后缀1（suf）的长度（两个方向最长连续1的数目）
-
讨论子区间是否全1，进行状态转移
-
```c++ #include
using namespace std; const int N = 50010; int ls(int p){ return p<<1; }
int rs(int p){ return p<<1|1;}
int tree[N<<2], pre[N<<2], suf[N<<2]; //tree:记录元素的值；pre:前缀1的个数；suf：后缀1的个数 int history[N]; //记录村庄被毁的历史 void push_up(int p,int len){ //len是结点p的长度 pre[p]=pre[ls(p)]; //父结点接收子结点的前缀信息 suf[p]=suf[rs(p)]; if(pre[ls(p)](len-(len>>1))) pre[p]=pre[ls(p)]+pre[rs(p)]; //左儿子都是1 if(suf[rs(p)](len>>1)) suf[p]=suf[ls(p)]+suf[rs(p)]; //右儿子都是1 } void build(int p, int pl,int pr){ if(pl==pr){tree[p]=pre[p]=suf[p]=1; return;} int mid = (pl+pr) >> 1; build(ls(p),pl,mid);
build(rs(p),mid+1,pr); push_up(p,pr-pl+1); } void update(int x, int c, int p, int pl, int pr){ if(pl==pr){ tree[p]=suf[p]=pre[p]=c; return; } //更新叶子结点信息 int mid=(pl+pr)>>1; if(x<=mid) update(x,c,ls(p),pl,mid); else update(x,c,rs(p),mid+1,pr); push_up(p,pr-pl+1); } int query(int x,int p,int pl,int pr){ if(pl==pr) return tree[p]; //返回叶子的值 int mid=(pl+pr)>>1; if(x<=mid){ //左子树 if(x + suf[ls(p)] > mid) return suf[ls(p)] + pre[rs(p)];//即从x一直连续到了mid，因此还要包含后面的pre else return query(x,ls(p),pl,mid); } else{ //右子树 if(mid + pre[rs(p)] >= x) return pre[rs(p)] + suf[ls(p)]; else return query(x,rs(p),mid+1,pr); } } int main(){ int n,m,x,tot;
while(scanf("%d%d",&n,&m)>0) { build(1, 1,n); tot = 0; while(m--){ char op[10]; scanf("%s",op); if(op[0]'Q'){scanf("%d",&x); printf("%d\n",query(x,1,1,n));} else if(op[0]'D'){ scanf("%d",&x); history[++tot]=x; //记录毁灭的历史 update(x,0,1,1,n); } else {x=history[tot--]; update(x,1,1,1,n); } //重建 } } }
```
扫描线¶
- 解决矩形面积并、矩形周长等问题
面积问题¶
- 从一个方向进行扫描（如途中从左到右）每个句型的宽很容易通过坐标作差得到，难点在于高的计算
- 将边划分，图中左边为入边，右边为出边；遇到入边就进入了一个矩形，遇到出边就离开了一个矩形
- 根据矩形的边界对边进行划分得到P1...P5，关心的就是何时使用那些边进行组合得到结果
-
用T1...T5表示是否使用对应的P，遇到入边时T+1遇到出边时T-1；实际的边就是由T>0的项组合得到的
-
-
算法的基本过程：（与上面这个图差90度）
-
读取矩形，记录入边和出边
-
将所有边按照y进行排序，确定扫描的顺序
-
对x轴做离散化
-
按照从低到高的顺序，用每条扫描线的线段更新线段树，每个节点的值是这层扫描新确定的新矩形面积
-
对所有矩形求和
-
```c++ #include
using namespace std; typedef long long ll; typedef unsigned long long ull; template inline void read(T &a) { T s = 0, w = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); } while(c >= '0' && c <= '9') { s = (s << 1) + (s << 3) + (c ^ 48); c = getchar(); } a = s*w; } int ls(int p){ return p<<1;}
int rs(int p){ return p<<1|1;} const int N =1e6; int Tag[N]; ll length[N]; int xx[N]; //存储扫描线 struct ScanLine{ ll y; ll right_x,left_x; int inout;//入边/出边 ScanLine(){} ScanLine(ll y,ll left_x,ll right_x,int inout):y(y),right_x(right_x),left_x(left_x),inout(inout){} bool operator < (const ScanLine &a) const{ return y<a.y; } }line[N]; void pushup(int p,int pl,int pr){ if(Tag[p]) length[p] = xx[pr]-xx[pl];//目前还没出，直接用 else if(pl+1 == pr) length[p] = 0;//叶节点 else length[p] = length[ls(p)]+length[rs(p)]; } void update(int l,int r,int io,int p,int pl,int pr){ if(l<=pl && pr<=r){ Tag[p] += io; pushup(p,pl,pr); return; } if(pl+1 == pr) return; //避免无限递归 int mid = (pl+pr)>>1; if(l<=mid) update(l,r,io,ls(p),pl,mid); if(r>mid) update(l,r,io,rs(p),mid,pr);//注意不是mid+1 pushup(p,pl,pr); } int main(){int n,cnt=0; read(n); //存储线，以及x用于离散化 for(int i=0;i
-
注意：每个节点代表的是一个线段（长度），如
1-2 3-4，因此pl+1 == pr作为叶节点条件；此外为了避免造成中间连接片段的缺失，不使用mid+1而是if(r>mid) update(l,r,io,rs(p),mid,pr);
周长问题：¶
-
计算重叠图形的总周长
-
法一：两次扫描，一次扫描横线一次扫描竖线，sum=对所有相邻扫描边做差取绝对值之和
-
基本思路与求解面积一致，也是以y排序，x用线段树进行维护
-
法二：一次扫描，计算横线同时计算（不完全在图像中）竖线的数目乘以高度计算，对于入边/出边的没有被覆盖的端点会引入/减少竖线
-
```c++ #include
using namespace std; int ls(int p){ return p<<1; }
int rs(int p){ return p<<1|1;}
const int N = 200005; struct ScanLine { int l, r, h, inout; //inout=1 下边, inout=-1 上边 ScanLine() {} ScanLine(int a, int b, int c, int d) :l(a), r(b), h(c), inout(d) {} }line[N]; bool cmp(ScanLine &a, ScanLine &b) { return a.h<b.h; } //y坐标排序 bool lbd[N<<2], rbd[N<<2]; //标记这个结点的左右两个端点是否被覆盖（0表示没有，1表示有） int num[N << 2]; //这个区间有多少条独立的边 int Tag[N << 2]; //标记这个结点是否有效 int length[N << 2]; //这个区间的有效宽度 void pushup(int p, int pl, int pr) { if (Tag[p]) { //结点的Tag为正，这个线段对计算宽度有效
lbd[p] = rbd[p] = 1; length[p] = pr - pl + 1; num[p] = 1; //每条边有两个端点 } else if (pl == pr) length[p]=num[p]=lbd[p]=rbd[p]=0;//叶子结点 else {
lbd[p] = lbd[ls(p)]; //和左儿子共左端点 rbd[p] = rbd[rs(p)]; //和右儿子共右端点 length[p] = length[ls(p)] + length[rs(p)]; num[p] = num[ls(p)] + num[rs(p)]; if (lbd[rs(p)] && rbd[ls(p)]) num[p] -= 1; //合并边 } } void update(int L, int R, int io, int p, int pl, int pr) { if(L<=pl && pr<=R){ //完全覆盖 Tag[p] += io; pushup(p, pl, pr); return; } int mid = (pl + pr) >> 1; if (L<= mid) update(L, R, io, ls(p), pl, mid); if (mid < R) update(L, R, io, rs(p), mid+1, pr); pushup(p, pl, pr); } int main() { int n; while (~scanf("%d", &n)) { int cnt = 0; int lbd = 10000, rbd = -10000; for (int i = 0; i < n; i++) { int x1,y1,x2,y2; scanf("%d%d%d%d", &x1,&y1,&x2,&y2); //输入矩形 lbd = min(lbd, x1); //横线最小x坐标 rbd = max(rbd, x2); //横线最大x坐标 line[++cnt] = ScanLine(x1, x2, y1, 1); //给入边赋值 line[++cnt] = ScanLine(x1, x2, y2, -1); //给出边赋值 } sort(line+1, line + cnt+1, cmp); //排序。数据小，不用离散化 int ans = 0, last = 0; //last：上一次总区间被覆盖长度 for (int i = 1; i <= cnt ; i++){ //扫描所有入边和出边 if (line[i].l < line[i].r) update(line[i].l, line[i].r-1, line[i].inout, 1, lbd, rbd-1); ans += num[1]*2 * (line[i + 1].h - line[i].h); //竖线 ans += abs(length[1] - last); //横线 last = length[1];
} printf("%d\n", ans); } return 0; }
```
*扩展线段树¶
二维线段树(树套树)¶
- 每个节点都是一颗线段树，对于两维(x,y)，可以先用x建立1维线段树，再有y在每个节点上建立2维线段树
- 单点插入（3指标），二维范围查询（2维限定范围，另一维找最大值）
#include<bits/stdc++.h>
using namespace std;
int ls(int p){ return p<<1; }
int rs(int p){ return p<<1|1;}
int n=1000, s[1005][4005]; //s[i][j]：身高区间i，活泼区间j的最大缘分
void subBuild(int xp, int p, int pl, int pr) { //建立第二维线段树：活泼度线段树
s[xp][p] = -1;
if(pl == pr) return;
int mid=(pl+pr)>>1;
subBuild(xp, ls(p), pl, mid);
subBuild(xp, rs(p), mid + 1, pr);
}
void build(int p,int pl, int pr) { //建立第一维线段树：身高线段树
subBuild(p, 1, 0, n);
if(pl == pr) return;
int mid=(pl+pr)>>1;
build(ls(p),pl, mid);
build(rs(p),mid + 1, pr);
}
void subUpdate(int xp, int y, int c, int p, int pl, int pr) {//更新第二维线段树
if(pl == pr && pl == y) s[xp][p] = max(s[xp][p], c);
else {
int mid=(pl+pr)>>1;
if(y <= mid) subUpdate(xp, y, c, ls(p), pl, mid);
else subUpdate(xp, y, c, rs(p), mid + 1, pr);
s[xp][p] = max(s[xp][ls(p)], s[xp][rs(p)]);
}
}
void update(int x, int y, int c, int p, int pl, int pr){ //更新第一维线段树：身高x
subUpdate(p, y, c, 1, 0, n); //更新第二维线段树：活泼度y
if(pl != pr) {
int mid=(pl+pr)>>1;
if(x <= mid) update(x, y, c, ls(p), pl, mid);
else update(x, y, c, rs(p), mid + 1, pr);
}
}
int subQuery(int xp, int yL, int yR, int p, int pl, int pr) { //查询第二维线段树
if(yL <= pl && pr <= yR) return s[xp][p];
else {
int mid=(pl+pr)>>1;
int res = -1;
if(yL <= mid) res = subQuery(xp, yL, yR, ls(p), pl, mid);
if(yR > mid) res = max(res, subQuery(xp, yL, yR, rs(p), mid + 1, pr));
return res;
}
}
int query(int xL, int xR, int yL, int yR, int p, int pl, int pr) {//查询第一维线段树
if(xL <= pl && pr <= xR) return subQuery(p, yL, yR, 1, 0, n);
//满足身高区间时，查询活泼度区间
else { //当前结点不满足身高区间
int mid = (pl+pr)>>1;
int res = -1;
if(xL <= mid) res = query(xL, xR, yL, yR, ls(p), pl, mid);
if(xR > mid) res = max(res, query(xL, xR, yL, yR, rs(p), mid + 1, pr));
return res;
}
}
int main(){
int t;
while(scanf("%d", &t) && t) {
build(1,100, 200);
while(t--) {
char ch[2]; scanf("%s", ch);
if(ch[0] == 'I') {
int h;double c, d; scanf("%d%lf%lf", &h, &c, &d);
update(h, c * 10, d * 10, 1, 100, 200);
} else {
int xL, xR, yL, yR; double c,d;
scanf("%d%d%lf%lf", &xL, &xR, &c, &d);
yL = c * 10, yR = d * 10; //转整数
if(xL > xR) swap(xL, xR);
if(yL > yR) swap(yL, yR);
int ans = query(xL, xR, yL, yR, 1,100, 200); //x：身高，y：活泼度
if(ans == -1) printf("-1\n");
else printf("%.1f\n", ans / 10.0);
}
}
}
return 0;
}
可持久化线段树¶
例题¶
-
c++ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int n,q; ll ls(ll p){return p<<1;} ll rs(ll p){return p<<1|1;} ll a[N],tree[N<<2],tag_add[N<<2],tag_mul[N<<2],mod; void push_up(ll p){ tree[p]=(tree[ls(p)]+tree[rs(p)])%mod; } void build(ll p,ll l,ll r){ tag_add[p]=0; tag_mul[p]=1; if(l==r){ tree[p]=a[l]; return; } ll mid=(l+r)>>1; build(ls(p),l,mid); build(rs(p),mid+1,r); push_up(p); } void addtag_add(ll p,ll pl,ll pr,ll k){ tree[p]=(tree[p]+(pr-pl+1)*k)%mod; tag_add[p]=(tag_add[p]+k)%mod; } void addtag_mul(ll p,ll pl,ll pr,ll k){ tree[p]=(tree[p]*k)%mod; tag_mul[p]=(tag_mul[p]*k)%mod; tag_add[p]=(tag_add[p]*k)%mod; } void push_down(ll p,ll pl,ll pr){ //先乘再加 if(tag_mul[p]!=1){ ll mid=(pl+pr)>>1; addtag_mul(ls(p),pl,mid,tag_mul[p]); addtag_mul(rs(p),mid+1,pr,tag_mul[p]); tag_mul[p]=1; } if(tag_add[p]){ ll mid=(pl+pr)>>1; addtag_add(ls(p),pl,mid,tag_add[p]); addtag_add(rs(p),mid+1,pr,tag_add[p]); tag_add[p]=0; } } void update_add(ll p,ll pl,ll pr,ll ql,ll qr,ll k){ if(ql<=pl&&pr<=qr){ addtag_add(p,pl,pr,k); return; } push_down(p,pl,pr); ll mid=(pl+pr)>>1; if(ql<=mid) update_add(ls(p),pl,mid,ql,qr,k); if(qr>mid) update_add(rs(p),mid+1,pr,ql,qr,k); push_up(p); } void update_mul(ll p,ll pl,ll pr,ll ql,ll qr,ll k){ if(ql<=pl&&pr<=qr){ addtag_mul(p,pl,pr,k); return; } push_down(p,pl,pr); ll mid=(pl+pr)>>1; if(ql<=mid) update_mul(ls(p),pl,mid,ql,qr,k); if(qr>mid) update_mul(rs(p),mid+1,pr,ql,qr,k); push_up(p); } ll query(ll p,ll pl,ll pr,ll ql,ll qr){ if(ql<=pl&&pr<=qr) return tree[p]; push_down(p,pl,pr); ll mid=(pl+pr)>>1; ll ans=0; if(ql<=mid) ans=(ans+query(ls(p),pl,mid,ql,qr))%mod; if(qr>mid) ans=(ans+query(rs(p),mid+1,pr,ql,qr))%mod; return ans; } int main() { cin>>n>>q>>mod; for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,1,n); for(int i=0;i<q;i++){ int type,x,y; cin>>type>>x>>y; if(type==3){ cout<<query(1,1,n,x,y)<<endl; } else{ int k; cin>>k; if(type==1){ update_mul(1,1,n,x,y,k); } else{ update_add(1,1,n,x,y,k); } } } return 0; } -
乘法加法两种tag，down时先乘法后加法
-
-
离散化+区间和+最值
-
区间和用来看区间内ip分配了多少，是否全部分配
-
最值计算分配给的人的id，（标记也存储这个），最大最小值一致表示分配给了相同的人
-
-
```c++ #include
using namespace std; typedef long long ll; const int N=15e4+10,M=5e4+10,K=170,B=32,INF=0x3f3f3f3f; struct segtree{ int n; struct node{int l,r,v,c,mn,mx;}e[N<<2]; #define l(p) e[p].l #define r(p) e[p].r #define v(p) e[p].v #define c(p) e[p].c #define mn(p) e[p].mn #define mx(p) e[p].mx void up(int p){ v(p)=v(p<<1)+v(p<<1|1); mn(p)=min(mn(p<<1),mn(p<<1|1)); mx(p)=max(mx(p<<1),mx(p<<1|1)); } void bld(int p,int l,int r){ l(p)=l;r(p)=r;c(p)=0; if(l==r){v(p)=0;mn(p)=INF;mx(p)=-INF;return;} int mid=l+r>>1; bld(p<<1,l,mid);bld(p<<1|1,mid+1,r); up(p); } void psd(int p){ //向下传递分配信息 if(c(p)){ v(p<<1)=r(p<<1)-l(p<<1)+1; mn(p<<1)=min(mn(p<<1),c(p)); mx(p<<1)=max(mx(p<<1),c(p)); c(p<<1)=c(p); v(p<<1|1)=r(p<<1|1)-l(p<<1|1)+1;
mn(p<<1|1)=min(mn(p<<1|1),c(p)); mx(p<<1|1)=max(mx(p<<1|1),c(p)); c(p<<1|1)=c(p); c(p)=0; } } void init(int _n){n=_n;bld(1,1,n);} //范围分配ip void chg(int p,int ql,int qr,int v){ if(ql>qr)return; if(ql<=l(p)&&r(p)<=qr){ v(p)=r(p)-l(p)+1; mn(p)=min(mn(p),v); mx(p)=max(mx(p),v); c(p)=v; return; } psd(p); int mid=l(p)+r(p)>>1; if(ql<=mid)chg(p<<1,ql,qr,v); if(qr>mid)chg(p<<1|1,ql,qr,v); up(p); } //范围查询 int cnt(int p,int ql,int qr){ if(ql<=l(p)&&r(p)<=qr)return v(p); int mid=l(p)+r(p)>>1,res=0; psd(p); if(ql<=mid)res+=cnt(p<<1,ql,qr); if(qr>mid)res+=cnt(p<<1|1,ql,qr); return res; } int amn(int p,int ql,int qr){ if(ql<=l(p)&&r(p)<=qr)return mn(p); int mid=l(p)+r(p)>>1,res=INF; psd(p); if(ql<=mid)res=min(res,amn(p<<1,ql,qr)); if(qr>mid)res=min(res,amn(p<<1|1,ql,qr)); return res; } int amx(int p,int ql,int qr){ if(ql<=l(p)&&r(p)<=qr)return mx(p); int mid=l(p)+r(p)>>1,res=-INF; psd(p); if(ql<=mid)res=max(res,amx(p<<1,ql,qr)); if(qr>mid)res=max(res,amx(p<<1|1,ql,qr)); return res; } }seg; int n,m,q,op,c; array```
- 扫描线的应用
珂朵莉树¶
-
适用范围是有区间赋值操作且数据随机的题目
-
思想在于随机数据下的区间赋值操作很可能让大量元素变为同一个数。所以我们以三元组
-
-
```c++ struct Node_t { int l, r; mutable int v; Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {} bool operator<(const Node_t &o) const { return l < o.l; } }; set
odt; auto split(int x) { if (x > n) return odt.end(); auto it = --odt.upper_bound(Node_t{x, 0, 0}); if (it->l == x) return it; int l = it->l, r = it->r, v = it->v; odt.erase(it);//分裂区间 odt.insert(Node_t(l, x - 1, v)); return odt.insert(Node_t(x, r, v)).first; }
void assign(int l, int r, int v) { auto itr = split(r + 1), itl = split(l); odt.erase(itl, itr); odt.insert(Node_t(l, r, v)); }
void performance(int l, int r) { auto itr = split(r + 1), itl = split(l); for (; itl != itr; ++itl) { // Perform Operations here //此处直接对v进行操作，因此上面设置为mutable //无论是赋值还是查询都直接进行 } } //使用 odt.insert(Node_t(1, n, 1)); ```
-
例子
-
第k小的数
ll kth(int l,int r,int k){
si itr=split(r+1),itl=split(l);
vector<pair<ll,int>> v;
v.clear();
for(si it=itl;it!=itr;++it)
v.push_back(pair<ll,int>(it->val,it->r-it->l+1));
sort(v.begin(),v.end());
for(int i=0;i<v.size();++i){
k -= v[i].second;
if(k<=0) return v[i].first;
}
return -1;//不存在
}
- 幂之和
//快速幂取模
ll qpow(ll a,int b,ll m){
ll t = 1ll;
a %= m;
while(b){
if(b&1) t= (t*a)%m;
a = (a*a)%m;
b>>=1;
}
return t;
}
//提取区间，暴力运算
ll query(int l,int r,int x,int y){
si itr=split(r+1),itl=split(l);
ll res(0);
for(si it=itl;it!=itr;++it)
res=(res+(it->r-it->l+1)*qpow(it->val,x,y))%y;
return res;
}
二叉搜索树¶
- 特点
- 每个节点的键值唯一
- 父节点比左节点的键值大，比右节点的键值小
- 按照中序遍历可以得到有序序列
- 平衡二叉树每个子树的根节点是子树的中位值
- 检索、删除、插入、排名、前去、后继的平均复杂度为\(O(logn)\)
- P3369 【模板】普通平衡树
替罪羊树¶
- 如果发现一棵树不平衡了，就删除子树，以中间元素为根重新建树（左右递归完成建树）
- 定义一个不平衡率，维护一个差不多平衡的二叉搜索树
-
取左子树/右子树节点数目占全部节点的比例作为不平衡率（取较大的子树，不平衡率在0.5-1）
-
操作
- 插入和重建：将新元素插入带空节点，之后判断是否平衡，不平衡则重建
-
删除和重建：为了避免删除元素造成的麻烦，使用标记删除、保留位置的方式，如果不平衡了就进行重建，同时移除已经删除的点
-
使用一个节点池维护使用的节点（重构时归还删除的节点）
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const double alpha = 0.75; //不平衡率。一般用alpha来表示
struct Node{
int ls,rs; //左右儿子
int val; //结点存的数字
int tot; //当前子树占用的空间数量，包括实际存储的结点和被标记删去的点
int size; //子树上实际存储数字的数量（便于快速获取元素的序号、根据下标获取元素）
int del; //=1表示这个结点存有数字，=0表示这个点存的数字被删了
}t[N];
int order[N],cnt; //order[]记录拍扁后的结果，即那些存有数字的结点。cnt是数量
int tree_stack[N],top = 0; //用一个栈来回收和分配可用的结点
int root = 0; //根结点，注意重建过程中根结点会变化
void inorder(int u){ //中序遍历，“拍平”摧毁这棵子树
if(!u) return; //已经到达叶子，退出
inorder(t[u].ls); //先遍历左子树
if(t[u].del) order[++cnt] = u; //如果该结点存有数字，读取它
else tree_stack[++top] = u; //回收该结点，等待重新分配使用
inorder(t[u].rs); //再遍历右子树
}
void Initnode(int u){ //重置结点的参数
t[u].ls = t[u].rs = 0;
t[u].size = t[u].tot = t[u].del = 1;
}
void Update(int u){
t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;
t[u].tot = t[t[u].ls].tot + t[t[u].rs].tot + 1;
}
//int rebuild_num=0; //测试：统计重建次数
void build(int l,int r,int &u){ //把拍扁的子树拎起来，重建
// rebuild_num++; //测试：统计重建次数
int mid = (l + r) >> 1; //新的根设为中点，使重构出的树尽量平衡
u = order[mid];
if(l == r){Initnode(u); return;} //如果是叶子，重置后返回
if(l < mid) build(l,mid - 1,t[u].ls);//重构左子树
if(l == mid) t[u].ls = 0; //注意这里，不要漏了
build(mid + 1,r,t[u].rs); //重构右子树
Update(u); //更新
}
void rebuild(int &u){ //重建。注意是&u
cnt = 0;
inorder(u); //先拍平摧毁
if(cnt) build(1,cnt,u); //再拎起，重建树
else u = 0; //特判该子树为空的情况
}
bool notbalance(int u){ //判断子树u是否平衡
if((double)t[u].size*alpha <=(double)max(t[t[u].ls].size,t[t[u].rs].size))
return true; //不平衡了
return false; //还是平衡的
}
void Insert(int &u,int x){ //插入数字x。注意是&u，传回了新的u
if(!u){ //如果结点u为空，直接将x插到这里
u = tree_stack[top--]; //从栈顶拿出可用的空结点
t[u].val = x; //结点赋值
Initnode(u); //其他参数初始化
return;
}
t[u].size++;
t[u].tot++;
if(t[u].val >= x) Insert(t[u].ls,x); //插到右子树
else Insert(t[u].rs,x); //插到左子树
if(notbalance(u)) rebuild(u); //如果不平衡了，重建这棵子树
}
int Rank(int u,int x){ //排名，x是第几名
if(u==0) return 0;
if(x>t[u].val) return t[t[u].ls].size+ t[u].del + Rank(t[u].rs, x);
return Rank(t[u].ls,x);
}
int kth(int k){ //第k大数是几?
int u = root;
while(u){
if(t[u].del && t[t[u].ls].size + 1 == k) return t[u].val;
else if(t[t[u].ls].size >= k) u = t[u].ls;
else{
k -= t[t[u].ls].size + t[u].del;
u = t[u].rs;
}
}
return t[u].val;
}
void Del_k(int &u,int k){ //删除排名为k的数
t[u].size--; //要删除的数肯定在这棵子树中，size减1
if(t[u].del && t[t[u].ls].size + 1 == k){
t[u].del = 0; //del=0表示这个点u被删除了，但是还保留位置
return;
}
if(t[t[u].ls].size + t[u].del >= k) Del_k(t[u].ls,k); //在左子树上
else Del_k(t[u].rs,k - t[t[u].ls].size - t[u].del); //在右子树上
}
void Del(int x){ //删除值为k的数
Del_k(root,Rank(root,x)+1); //先找x的排名，然后用Del_k()删除
if(t[root].tot * alpha >= t[root].size)
rebuild(root); //如果子树上被删除的结点太多，就重构
}
/*
void print_tree(int u){ //测试：打印二叉树，观察
if(u){
cout<<"v="<<t[u].val<<",l="<<t[u].ls<<",r="<<t[u].rs<<endl;
print_tree(t[u].ls);
print_tree(t[u].rs);
}
}
int tree_deep[N]={0},deep_timer=0,max_deep=0; //测试
void cnt_deep(int u){ //测试：计算二叉树的深度
if(u){
tree_deep[u]=++deep_timer; //结点u的深度
max_deep = max(max_deep,tree_deep[u]); //记录曾经的最大深度
cnt_deep(t[u].ls);
cnt_deep(t[u].rs);
deep_timer--;
}
} */
int main(){
for(int i=N-1;i>=1;i--) tree_stack[++top] = i; //把所有可用的t[]记录在这个栈里面
int q; cin>>q;
// rebuild_num = 0;deep_timer=0;max_deep=0; //测试
while(q--){
int opt,x; cin >> opt >> x;
switch (opt){
case 1: Insert(root,x); break;
case 2: Del(x); break;
case 3: printf("%d\n",Rank(root,x)+1); break;
case 4: printf("%d\n",kth(x)); break;
case 5: printf("%d\n",kth(Rank(root,x))); break;
case 6: printf("%d\n",kth(Rank(root,x+1)+1)); break;
}
// cout<<">>"<<endl;print_tree(root);cout<<endl<<"<<"<<endl; //测试：打印二叉树
// cnt_deep(root); //测试：计算曾经的最大深度
}
// cout<<"rebuild num="<<rebuild_num<<endl; //测试：打印重建次数
// cout<<"deep="<<max_deep<<endl; //测试：打印替罪羊树的最大深度
return 0;
}
笛卡尔树¶
- 笛卡尔树一次构建，不支持修改，只支持查询
-
笛卡尔树可以用于处理同时要求二叉树和堆两种性质的问题
-
treap的value是随机值，是为了使树更加平衡引进的，而笛卡尔树的value是一个确定的值。
- 可以使用下标作为键值，使用值作为优先级辅助构建，是下标的二叉搜索树
- 可以方便的通过下标检索元素、以及删除插入等
- 单调栈建树，复杂度\(O(n)\)
- 将新插入的点插入到根节点最右链
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <stack>
using namespace std;
const int N = 50005;
const int INF = 0x7fffffff;
struct Node{
char s[100]; int ls,rs,fa,pri;
friend bool operator<(const Node& a,const Node& b){
return strcmp(a.s,b.s)<0;}
}t[N];//静态创建
void buildtree2(int n){ //用栈来辅助建树
stack <int> ST; ST.push(0); //t[0]进栈，它一直在栈底
for(int i=1;i<=n;i++){
int pos = ST.top();
while(!ST.empty() && t[pos].pri < t[i].pri){
pos = t[ST.top()].fa;
ST.pop(); //把比i优先级小的弹出栈
}
t[i].ls = t[pos].rs;
t[t[i].ls].fa = i;
t[pos].rs = i;
t[i].fa = pos;
ST.push(i); //每个结点都一定要进栈
}
}
void inorder(int x){ //中序遍历打印
if(x==0) return;
printf("(");
inorder(t[x].ls); printf("%s/%d",t[x].s,t[x].pri); inorder(t[x].rs);
printf(")");
}
int main(){
int n;
while(scanf("%d",&n),n){
for(int i=1;i<=n;i++){
t[i].ls = t[i].rs = t[i].fa = 0; //有多组测试，每次要清零
scanf(" %[^/]/%d", t[i].s, &t[i].pri); //注意输入的写法
}
t[0].ls = t[0].rs = t[0].fa = 0; //t[0]不用，从t[1]开始插结点
t[0].pri = INF; //t[0]的优先级无穷大
sort(t+1,t+1+n); //对标签先排序，非常关键。这样建树时就只需要考虑优先级pri（使用下标做键值时无需排序，天然有序）
buildtree2(n);
inorder(t[0].rs); //t[0]在树的最左端，第一个点是t[0].rs
printf("\n");
}
return 0;
}
RMQ问题¶
-
通常笛卡尔树选择数列下标作为键值，可以很方便的实现查询区间最大值等功能，这与st、线段树等效率是类似的
-
由于笛卡尔树是一个堆结构，因此RMQ查询就是寻找LCA
- 最大子矩形问题
- 以下标作为键，高度作优先级，只需要统计每个节点可以到达最左侧和最右侧节点，也就是宽度，根节点的优先级就是高度（小根堆）
- P1377 树的序
- 将元素的大小作为键（题目要求符合二叉搜索树性质）
- 将元素的小标作为优先级（题目要求后面的节点更晚插入，即是前面节点的子节点）
- 最后以前序遍历得到节点构建顺序
Treap树(树堆)¶
- 基于键值（BST）+优先级(堆)
- 对于树上的点除了满足常规二叉树的特性还要满足堆的性质，用优先级来维护二叉树的平衡性
- 键值和优先级分别维护二叉树的水平和纵向排列
- 如果每个节点的键值和优先级是确定且不同的，那么树的形态是唯一的
- 不过优先级是在插入过程中动态分配的（如果需要动态调整节点），因此不能提前预知树的形态，通常随机分配一个优先级
- 建树\(O(nlogn)\)
调整和维护¶
旋转法¶
- 插入节点
- 根据键值插入到空的叶节点
- 通过旋转使得优先级符合（旋转不会破坏键值关系）
- 删除节点
- 如果被删除节点有两个子节点，那么就把优先级高的向上旋转（即被删除节点下移），直至被删除节点称为叶节点可以直接删除
- 检索及序号
- 通过维护子树size递归计算
#include<bits/stdc++.h>
using namespace std;
const int M=1e6+10;
int cnt = 0; //t[cnt]: 最新结点的存储位置
struct Node{
int ls,rs; //左右儿子
int key,pri; // key：键值；pri：随机的优先级
int size; //当前结点为根的子树的结点数量，用于求第k大和rank
}t[M]; //tree[]，存树
void newNode(int x){ //初始化一个新结点
cnt++; //从t[1]开始存储结点，t[0]被放弃。若子结点是0，表示没有子结点
t[cnt].size = 1;
t[cnt].ls = t[cnt].rs = 0; //0表示没有子结点
t[cnt].key = x; //key: 键值
t[cnt].pri = rand(); //pri：随机产生，优先级（利用随机维护平衡）
}
void Update(int u){ //更新以u为根的子树的size
t[u].size = t[t[u].ls].size + t[t[u].rs].size+1;
}
void rotate(int &o,int d){ //旋转，参考图示理解。 d=0右旋，d=1左旋
int k;
if(d==1) { //左旋，把o的右儿子k旋到根部
k=t[o].rs;
t[o].rs=t[k].ls;//图中的x
t[k].ls=o;
}
else { //右旋，把o的左儿子k旋到根部
k=t[o].ls;
t[o].ls=t[k].rs; //图中的x
t[k].rs=o;
}
t[k].size=t[o].size;
Update(o);
o=k; //新的根是k
}
void Insert(int &u,int x){
if(u==0){newNode(x);u=cnt;return;} //递归到了一个空叶子，新建结点
t[u].size++;
if(x>=t[u].key) Insert(t[u].rs,x); //递归右子树找空叶子，直到插入
else Insert(t[u].ls,x); //递归左子树找空叶子，直到插入
if(t[u].ls!=0 && t[u].pri<t[t[u].ls].pri) rotate(u,0);
if(t[u].rs!=0 && t[u].pri<t[t[u].rs].pri) rotate(u,1);
Update(u);
}
void Del(int &u,int x){
t[u].size--;
if(t[u].key==x){
if(t[u].ls==0&&t[u].rs==0){u=0; return;}
if(t[u].ls==0||t[u].rs==0){u=t[u].ls+t[u].rs; return;}
if(t[t[u].ls].pri < t[t[u].rs].pri)
{ rotate(u,0); Del(t[u].rs, x); return;}
else{ rotate(u,1); Del(t[u].ls, x); return;}
}
if(t[u].key>=x) Del(t[u].ls,x);
else Del(t[u].rs,x);
Update(u);
}
int Rank(int u,int x){ //排名，x是第几名
if(u==0) return 0;
if(x>t[u].key) return t[t[u].ls].size+1+Rank(t[u].rs, x);
return Rank(t[u].ls,x);
}
int kth(int u,int k){ //第k大数是几?
if(k==t[t[u].ls].size+1) return t[u].key; //这个数为根
if(k> t[t[u].ls].size+1) return kth(t[u].rs,k-t[t[u].ls].size-1);//右子树
if(k<=t[t[u].ls].size) kth(t[u].ls,k); //左子树
}
//可能存在相同元素，因此复杂
int Precursor(int u,int x){//即小的中最大的
if(u==0) return 0;
if(t[u].key>=x) return Precursor(t[u].ls,x);//第一个小于的元素
int tmp = Precursor(t[u].rs,x);
if(tmp==0) return t[u].key;
return tmp;
}
int Successor(int u,int x){
if(u==0) return 0;
if(t[u].key<=x) return Successor(t[u].rs,x);
int tmp = Successor(t[u].ls,x);
if(tmp==0) return t[u].key;
return tmp;
}
int main(){
srand(time(NULL));
int root = 0; //root是整棵树的树根，0表示初始为空
int n; cin>>n;
while(n--){
int opt,x; cin >> opt >> x;
switch (opt){
case 1: Insert(root,x); break;
case 2: Del(root,x); break;
case 3: printf("%d\n",Rank(root,x)+1); break;
case 4: printf("%d\n",kth(root,x)); break;
case 5: printf("%d\n",Precursor(root,x)); break;
case 6: printf("%d\n",Successor(root,x)); break;
}
}
return 0;
}
FHQ法¶
FHQ Treap的应用¶
Splay树¶
K-D树¶
- 用来多维上的问题，如平面上任一点距离最近的另一点；矩形范围内点的数目等
- 使用二分法+二叉树，交替利用二分中间节点进行横竖划分，将平面内点的关系转化为了一棵树
动态树与LCT¶
有序集合¶
- 通常使用multiset以及multimap，但是这类问题往往有效率更高的复杂解法
例题¶
- 456. 132 模式
- 使用单调栈的效率更高