前言
替罪羊树是一种平衡树。对于平衡树的二叉搜索树性质，已经在这个博客比较详细地提到过了。那篇博客内，详细讲了的平衡树是 Splay。注意到 Splay 维护平衡的时候会直接通过旋转改变树的结构，在写平衡树套什么东西的时候，Splay 维护起来可能会有写吃力。因此这里重点写一下替罪羊树。
KD-Tree 和替罪羊树维护树平衡的方法一样，因此也可以提出来讲讲。
其实重点是KD不是替罪羊
替罪羊树
平衡树的插入，删除等操作基本都是一致的，重要的是如何维护树的平衡。例如给出一个不太平衡的树：
虽然单次查询不至于退化成 ，但相对 的级别也够慢了。我们发现比较不平衡的两个典型，就是 和 的两个子树。
替罪羊树的思想很简单，现在既然这两个地方不平衡，那我直接把这两个子树重建一下就可以了。
平衡多了。但是众所周知，我不能每次修改一下就要全部重新把不平衡的地方重建。为了保证复杂度，应该需要衡量一个平衡因子 ，其中 ，如果一个节点的左右子树中，较大的那个子树占比达到了 ，就给这个子树重构一下。合适的 可以控制替罪羊树的复杂度。
一般而言， 取到 就够了。如果你的 取到了 才能保证不出锅，多半就是写假了。没有写假、平衡因子设置合理的替罪羊树单次操作复杂度基本 级。
具体的重构实现，可以先把要重构的子树拍扁，即按照中序遍历得到对应的序列，然后对于这个序列重新构建子树即可。每次重新构建的时候，应该以中位数对应的节点当作根节点，因为前面是在替罪羊树上中序遍历得到的序列，已经有序了，直接取中间位置就是中位数。
和 Splay 不同的地方还有替罪羊的删除操作。替罪羊树并不能很好地直接删除，因此通常以打标记的方法，如果这个数字被删掉了（出现次数为 ），在下一次重构的时候碰到这个点就不管它了。如果写的简单一点也可以直接忽视删除操作，保留原节点，大部分情况都不会被卡。
具体细节可以参考如下代码：
struct SheepTree{
int root,tot,tmp;
int pb[max_n]; // 记录拍扁时的中序遍历数组
SheepTree(){root=tot=tmp=0;}
const double alpha=0.75;
struct dot{
int ls,rs,sz,cnt,sd,sm,val; // 左右儿子、sz、出现次数、sd、sm、维护的值
dot(){ls=rs=sz=cnt=sd=sm=val=0;}
}a[max_n];
#define ls(x) (a[x].ls)
#define rs(x) (a[x].rs)
inline void resize(int &x){
a[x].sz=a[ls(x)].sz+a[rs(x)].sz+(bool)(a[x].cnt); // sz 去掉删掉的点的子树大小
a[x].sd=a[ls(x)].sd+a[rs(x)].sd+1; // 直接统计节点数的子树大小（数重复出现算一次）
a[x].sm=a[ls(x)].sm+a[rs(x)].sm+a[x].cnt; // 统计子树对应了实际上的多少个数（重复出现算多次）
}
inline bool regain(int &x){ // 判断需不需要重构
if(!a[x].sm) return 0; // 被删掉了
return (alpha*a[x].sd<=max(a[ls(x)].sd,a[rs(x)].sd) || alpha*a[x].sd>=a[x].sz);// 子树不平衡，或者删掉了比较多的点影响平衡
}
inline void get(int x){ // 中序遍历得到拍扁序列
if(ls(x)) get(ls(x));
if(a[x].cnt) pb[++tmp]=x;
if(rs(x)) get(rs(x));
}
inline int build(int l,int r){ // 建树（重构）
if(l==r){
ls(pb[l])=rs(pb[l])=0;
resize(pb[l]);
return pb[l];
}
int mid=(l+r)>>1; // 取中间位置对应的节点，重造
ls(pb[mid])=rs(pb[mid])=0;
if(l<=mid-1) ls(pb[mid])=build(l,mid-1); // 读取左右儿子关系
if(r>=mid+1) rs(pb[mid])=build(mid+1,r);
resize(pb[mid]);
return pb[mid]; // 返回当前子树的根节点
}
inline void rebuild(int &x){ // 重构树的全流程
tmp=0;
get(x); // 中序遍历
x=build(1,tmp); // 重构这个点的子树
}
inline void pushup(int &x){ // 更新节点
resize(x); // 更新大小等信息
if(regain(x)) rebuild(x); // 如果需要则重构
}
// 剩下的都是板子了
inline void insert(int &x,int val){
if(!x){
x=++tot;
a[x].val=val,a[x].cnt=1;
resize(x);
return;
}
if(val==a[x].val) ++a[x].cnt;
else if(val<a[x].val) insert(ls(x),val);
else insert(rs(x),val);
pushup(x);
}
inline void delet(int &x,int val){
if(a[x].val==val) --a[x].cnt;
else if(val<a[x].val) delet(ls(x),val);
else delet(rs(x),val);
pushup(x);
}
inline int rank(int &x,int val){
if(!x) return 1;
if(val==a[x].val) return a[ls(x)].sm+1;
else if(val<a[x].val) return rank(ls(x),val);
else return a[ls(x)].sm+a[x].cnt+rank(rs(x),val);
}
inline int kth(int &x,int k){
if(!x) return -1;
if(k>a[ls(x)].sm && k<=a[ls(x)].sm+a[x].cnt) return a[x].val;
else if(k<=a[ls(x)].sm) return kth(ls(x),k);
else return kth(rs(x),k-a[ls(x)].sm-a[x].cnt);
}
inline int pre(int val){
return kth(root,rank(root,val)-1);
}
inline int suf(int val){
return kth(root,rank(root,val+1));
}
}shp;
KD-Tree
建树
KD-Tree 是一个优雅的暴力，复杂度相对可观，但是比较裸的 KD-Tree 容易被卡常。来看一下这样一个题目：
例题：在线地支持两个在平面直角坐标系上的操作：插入一个坐标为 ，点权为 的点，查询一个矩形范围内的点权和。操作数 ，点权和坐标在 范围内，时间限制 3s，空间限制 20MB。
强制在线叉掉了 CDQ，20MB 的空间限制叉掉了树套树，真是毒瘤妈妈给毒瘤开门——毒瘤到家了。
因此我们就需要一个更加优秀的数据结构，可以很好地处理这个问题。KD-Tree 就是一个不错的选择。我们知道平衡树可以做到在一维（序列）的空间上对点进行很多高级的操作，KD-Tree 就是针对 K 维空间进行的。
为了简单画图和叙述，以二维空间为例子，看看这样子一个平面。
如果是在一个一维序列上，我们就会遵循 BST 的性质，每次取当前区间的中位数作为根，然后递归地建树。这样建出来的树一定具有 SBT 性质，随后怎么在加点删点时维护平衡就是它自己的事情了。
如果能找到一个标准，使得平面上的点也能建在一个树上，然后尽可能地满足 SBT 性质，那么复杂度就是接近 级别的。
KD-Tree 并不把事情搞的很复杂，每次我们只需要选择一个维度，然后在当前区间内找到中位数位置划分即可。当然每次选择维度不宜都是同一个，不然非常容易退化，常见的方法是交替选维度。
例如先选择 轴为根的选择标准，找到点 。
然后换一个维度，即 轴维度，在得到的两个区间中各找到中位数点，注意到 在同一线上，为了方便处理就随便选一个，另一个到时候再分。这里假设选择的是为 ， 和 视为在同一区域，不和 同一区域。
然后再按照 轴分一下，再按照 轴……以此类推，最后得到的图可能是这样：
然后按照划分的顺序，假设对于 轴，左边为左子树部分，右边为右子树部分；对于 轴，上面为左子树部分，下面为右子树部分，就可以得到这样的一个树：
我们发现这个树看起来挺平衡的，那就可以根据这个关系来建树就行，控制了随机数据下在树上进行的操作复杂度约为 级别。
至于如何找到中位数，可以用 nth_element 函数，可以 找到一个序列的中位数并把它放在目标位置。
重构
这样就出现了一个问题，因为加点的时候一定是加在一个叶子上的，如果我一直往一个区域加一堆点，这个子树的根就不一定是原来的中位数了。然后加着加着这个树就不平衡了，复杂度就退化了。
只需要和替罪羊树一样，搞上一个平衡因子 ，如果子树之间不平衡了就暴力拆下来重构即可。可以发现只要 定得好，复杂度还可以稳定在 级别。
然后到这里上面那个例题就可以做出来了，我们再维护一下一个点子树内的点权和，这个点本身的点权，和子数内所有点构成的最大矩形。询问的时候，如果询问矩形和这个点涵盖的矩形相离，不会造成贡献，如果询问区间包含了这个点涵盖的矩形，则直接返回这个点的子树点权和。
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
using namespace std;
bool Begin;
const int max_n=200055;
inline int read(){
int x=0;bool w=0;char c=getchar();
while(c<'0' || c>'9') w|=c=='-',c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w?-x:x;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
}
inline bool interv(int mid,int l,int r){ // 判断 x 是否在区间 [l,r] 内
if(l<=mid && mid<=r) return 1;
return 0;
}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
struct point{
int x,y,val; // 横纵坐标，权值
point(){x=y=val=0;}
}pos[max_n];
inline point makep(int a,int b,int c){
point res;
res.x=a,res.y=b,res.val=c;
return res;
}
bool cmpt=0;
inline bool cmp(point i,point j){ // 根据 cmpt 决定是横坐标比较还是纵坐标比较
if(cmpt) return i.x<j.x;
return i.y<j.y;
}
int fre[max_n],tp; // 删除节点时腾出的空间，垃圾回收
struct KD_Tree{
const double alpha=0.75; // 平衡因子
int root,tot,tmp;
bool chgr;
KD_Tree(){root=tot=tmp=0;}
inline int newnode(){ // 前面说的垃圾回收在这里用到了
int x;
if(tp) x=fre[tp--];
else x=++tot;
return x;
}
struct dot{
point x,l,r;// 这个点位置，涵盖的矩形的左上角和右下角
int tp,sz,ls,rs,sm; // 以哪个维度分，子树大小，左右儿子，子数点权和
dot(){tp=sz=ls=rs=sm=0;}
}a[max_n];
#define ls(x) (a[x].ls)
#define rs(x) (a[x].rs)
inline void pushup(int x){
a[x].l=a[x].r=a[x].x,a[x].sm=a[x].x.val; // 初始化信息
a[x].sz=a[ls(x)].sz+a[rs(x)].sz+1; // 更新子树大小
if(ls(x)){ // 维护子树点权和以及涵盖矩形
a[x].sm+=a[ls(x)].sm;
a[x].l.x=min(a[x].l.x,a[ls(x)].l.x),a[x].r.x=max(a[x].r.x,a[ls(x)].r.x);
a[x].l.y=min(a[x].l.y,a[ls(x)].l.y),a[x].r.y=max(a[x].r.y,a[ls(x)].r.y);
}
if(rs(x)){
a[x].sm+=a[rs(x)].sm;
a[x].l.x=min(a[x].l.x,a[rs(x)].l.x),a[x].r.x=max(a[x].r.x,a[rs(x)].r.x);
a[x].l.y=min(a[x].l.y,a[rs(x)].l.y),a[x].r.y=max(a[x].r.y,a[rs(x)].r.y);
}
}
inline int build(int l,int r,int t){ // 建树，t 为当前划分维度
int x=newnode(),mid=(l+r)>>1;
cmpt=t;
nth_element(pos+l,pos+mid,pos+r+1,cmp);
a[x].tp=t,a[x].x=pos[mid],ls(x)=rs(x)=0;
if(l<=mid-1) ls(x)=build(l,mid-1,t^1); // 交替划分
if(r>=mid+1) rs(x)=build(mid+1,r,t^1);
pushup(x);
return x;
}
inline void get(int x){ // 和替罪羊一样，先拍扁
if(ls(x)) get(ls(x));
pos[++tmp]=a[x].x,
fre[++tp]=x;
if(x==root) chgr=1;
if(rs(x)) get(rs(x));
}
inline void rebuild(int &x){ // 重新构造这个子树
if(alpha*a[x].sz>max(a[ls(x)].sz,a[rs(x)].sz)) return; // 不需要重构
tmp=0,chgr=0;
get(x);
x=build(1,tmp,0);
if(chgr) root=x;
}
inline void insert(int &x,point pt,int t){ // 添加一个点，用 t 这个方法划分维度
if(!x){
x=newnode();
a[x].sz=1,a[x].x=pt,a[x].tp=t;
pushup(x);
return;
}
cmpt=t;
if(cmp(pt,a[x].x)) insert(ls(x),pt,t^1); // 交替划分
else insert(rs(x),pt,t^1);
pushup(x),rebuild(x);
}
inline int ask(int x,point i,point j){ // 询问区间和
if(!x || a[x].l.x>j.x || a[x].r.x<i.x || a[x].l.y>j.y || a[x].r.y<i.y) return 0; // 不存在该点或者与询问矩形相离
if(a[x].l.x>=i.x && a[x].r.x<=j.x && a[x].l.y>=i.y && a[x].r.y<=j.y) // 能涵盖到的矩形被询问矩形涵盖
return a[x].sm;
int res=0;
if(interv(a[x].x.x,i.x,j.x) && interv(a[x].x.y,i.y,j.y)) res+=a[x].x.val; // 该点本身在询问矩形内
res+=ask(ls(x),i,j)+ask(rs(x),i,j);
return res;
}
}kdt;
bool ndp=0,End; // ndp 表示是否强制在线
signed main(){
//cerr<<"Memory: "<<1.0*(&Begin-&End)/1024/1024<<"MB\n"<<"\n";
int lst=read();lst=0;
while(1){
int op=read();
if(op==1){
int x=read(),y=read(),z=read();
if(ndp) x^=lst,y^=lst,z^=lst;
kdt.insert(kdt.root,makep(x,y,z),0); // 插入一个点
}
if(op==2){
int x=read(),y=read(),a=read(),b=read();
if(ndp) x^=lst,y^=lst,a^=lst,b^=lst;
write(lst=kdt.ask(kdt.root,makep(x,y,0),makep(a,b,0))),putchar('\n'); // 矩形范围用两个点来表示
}
if(op==3)
break;
}
return 0;
}
实测最慢的点不超过 2s。事实上，交替选点的复杂度一般视为单次树上操作 级别的。
估价
假设把求矩形内点权和，改成查询离一个点的曼哈顿距离最近的点的距离。
我们发现上面的划分方法有一个很大的弊端，就是有可能一个点和另一个点很近，但是在树上并不出在相邻的位置。举个例子，上面那个图（如果懒得翻，这里也放一个）：
和 最近的点是 ，但是显然 和 不成相邻关系。如果右边这一部分画得分散一点，搞不好离 最近的是 ，那就连祖先关系都不是。
因此每次询问的时候，就只能暴力跑一遍整个树吗？那我还建这个树干嘛。因此需要考虑怎么进行优化。
如果当前我找到的这个点，它的能涵盖到的矩形，距离询问点的距离还大于等于当前找到的最优答案，那还要往这个点的子树找干什么。
这样的看起来显然的优化实际上可以让复杂度变得非常优秀。确定好一个合适的搜索顺序后，基本可以看为也是根号级别的。这就是 KD-Tree 的估价。
这里给出一个例子。
inline int check(int x,int i){ // 估价函数
if(!x) return inf; // 不存在这个点，显然不能往这里搜
return max(a[x].l.x-d[i].x,0)+max(d[i].x-a[x].r.x,0)+max(a[x].l.y-d[i].y,0)+max(d[i].y-a[x].r.y,0); // 点到矩形曼哈顿距离最小值
}
inline void query(int x,int id){
if(a[x].id!=id) // 查寻点和我现在的点不同，更新答案
ans=min(ans,abs(a[x].x.x-d[id].x)+abs(a[x].x.y-d[id].y));
int al=check(ls(x),id),ar=check(rs(x),id); // 计算左右子树估价
if(al<ar){ // 哪个子树更近，先走哪个，使得较优的答案更早算出来，减枝更多
if(al<ans) query(ls(x),id); // 如果到矩形的距离都比当前的最有答案大，别走
if(ar<ans) query(rs(x),id);
}
else{
if(ar<ans) query(rs(x),id);
if(al<ans) query(ls(x),id);
}
}
例题
BZOJ2683 简单题
题目连接，就是上面引入 KD-Tree 的例题。
luogu4169 天使玩偶
题目连接，就是改成求曼哈顿距离最近的这个题。
BZOJ3489 A simple rmq problem
题目连接，大概题意如下：
对于一个给定的序列，要求强制在线地处理若干询问，每次询问给定 求 内最大的一个数字，满足这个数字在区间中只出现了一次。
。
简要题解
先求出每个数字上一次出现的位置和后一次出现的位置，问题转化为找到最大的一个数，使得其上一次出现位置在左端点前，下一次出现位置在右端点后。那么不妨以这个点的位置、这个数上次出现位置、这个数字下一次出现位置三个维度为坐标，值为点权，建立一个 3D-Tree。每次查询的时候在 3D-Tree 上找到符合条件的点的点权最大值即可。可以参阅我的 KD-Tree 代码。
BZOJ4154 Generating Synergy
题目连接，大概题意如下：
对于一个有根带点权树，支持两个操作：一是修改 子树与 距离不超过 的点的点权，二是查询一个点的点权。
。
简要题解
二维线段树显然可以做这个题，现在考虑如何用 KDTree 解决。如果我们求出树上每个点的深度和其对应子树的 dfn 区间，记为 dep[i],dfn[i],out[i]。
那么对于一个点的子树修改，等价于修改满足 dfn[i] 在 dfn[x] 和 out[x] 之间，且 dep[i] 在 dep[x] 和 dep[x]+k 之间的点 i 的权值。
因此不妨用 dfn[i] 和 dep[i] 当作一个点的横坐标和纵坐标，单次修改就相当于矩形内所有点赋值、单点查寻。因为不需要动态地加点删点，只需要给 KD-Tree 搞上一个区间赋值的下传标记即可实现。
具体代码可以参考我的提交记录
